BFS (29) 썸네일형 리스트형 [백준 / BOJ] 2917 늑대 사냥꾼 문제 출처 : www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 늑대 현우는 사냥꾼을 피해서 최대한 안전한 경로로 집으로 도착해야한다. 사냥꾼은 나무뒤에 숨어있다. N*M 배열이 주어지고, 나무의 위치는 +, 현우의 위치는 V, 오두막의 위치는 J로 주어진다. 현우의 위치에서 집까지 가는 가장 안전한 경로에서 나무와 현우의 거리의 최솟값을 출력하는 문제다. 풀이 BFS를 돌려서 나무와 모든정점들에 최단거리를 저장해주고, 현우의 위치를 기준으로 다익을 돌려 가장 안전한 .. [백준 / BOJ] 1113 수영장 만들기 문제 출처 : www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net N*M크기의 칸에 수영장을 만들려고 한다. 각 칸에 그 땅이 갖고있는 높이가 주어졌을때, 수영장에 물을 얼만큼 넣을수있는지 구하는 문제이다. 만약 수영장이 다음과 같다면, 16661 61116 16661 가운데 3개의칸에 5씩 넣어서 총 15만큼의 물을 넣을수있다. 만약 5보다 더 많이 넣는다면 수영장 벽의 높이인 6보다 커져서 물이 넘친다. 풀이 한달전에 풀었던 문제였다... [백준 / BOJ] 2206 벽 부수고 이동하기 문제 출처 : www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net N*M행렬이 주어진다. 이때, 이동할수있는곳은 0 벽이있어서 이동할수 없는곳은 1로 표시된다. 이동할때 벽을 최대 1회 부수고 이동할수있는데, 1,1에서 시작해서 N,M에 도달했을때 최단경로를 구하는 문제다. 풀이 BFS문제다. 일반적인 BFS와 check배열을 선언하는게 다른데, 3차원 체크배열을 선언해서 해당 지점에 벽을 부수고 이동한 경로와 최솟값과 벽을 부수지 .. [백준 / BOJ] 1261 알고스팟 문제 출처 : www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net N*M크기의 미로가 주어진다. 미로는 0,1로 주어지며 0은 빈 방 1은 벽이다. 알고스팟 운영진이 (1,1)에서 (N,M)으로 이동할때까지 총 몇개의 벽을 부숴야하는지 구하는 문제이다. 풀이 다익스트라를 이용해서 푸는문제다. 벽을 부순 횟수를 저장하는 배열을 만들고 배열의 모든칸을 최댓값으로 초기화 시켜준다. (나는 1000000000로 초기화 해줬음) 위 배열에는 해당 (.. [백준 / BOJ] 6118 숨바꼭질 문제 출처 : www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 이전 1 2 3 4 다음