미로 탐색(2178번)

• 티어 : Sliver 1
• 정답여부 : 정답
• 알고리즘 유형 : 그래프 이론, 그래프 탐색,너비 우선 탐색
• 시간 제한 : 오답

💡문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

💡입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

💡출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

💡예제 입력 1

4 6
101111
101010
101011
111011

💡예제 출력 1

15

💡예제 입력 2

4 6
110110
110110
111111
111101

💡예제 출력 2

9

💡예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

💡예제 출력 3

38

💡예제 입력 4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

💡예제 출력 4

13

💡문제요약

각 배열에 1, 0이 있는데 1은 움직일수 있는 칸 0 은 움직일수 없는 칸이다. N M 의 위치까지 최소 갈수 있는 칸을 구하면 되는 문제

💡알고리즘 설계

• N : 세로
• M : 가로

1. 각 값을 넣어준다.
2. 0,0 시작 배열의 시작은 0임으로 1,1 시작과 같다.
3. 각 인접한 위치에서 방문하지 않았고 0이 아닌 1을 확인
4. 만족하면 큐에 추가하고 방문처리
5. 그리고 현재 위치까지 오는데 걸린 거리 1을 저장

💡작성코드

• Java

package algorithms_Java02_6;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class baekjoon_2178 {
	static int N, M;
	static int arr[][];
	static boolean visit[][];
	static int [] dx = {-1, 1, 0, 0};
	static int [] dy = {0, 0, -1, 1};
		public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int [N][M];
		visit = new boolean[N][M];
		for(int i =0; i < N; i++) {
			String row = br.readLine();
			for(int j = 0; j < M; j++) {
				arr[i][j] = row.charAt(j) - '0';
			}
		}
		visit[0][0] = true;
		bfs(0,0);
		System.out.println(arr[N-1][M-1]);	
	}
		public static void bfs(int x, int y) {
			Queue<int[]> que = new LinkedList<>();
			que.offer(new int[] {x, y});
			visit[x][y] = true;
			while(!que.isEmpty()) {
				int[] poll = que.poll();
				int poll_x = poll[0];
				int poll_y = poll[1];
				for(int i = 0; i < 4; i++) {
					int next_x = dx[i] + poll_x;
					int next_y = dy[i] + poll_y;
					if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < M && !visit[next_x][next_y] && arr[next_x][next_y] == 1) {
						que.offer(new int[] {next_x,next_y}); 
						visit[next_x][next_y] = true; // 체크
						? 이동거리 어떻게 ?
					}
				}
			}
		}
}

💡시간복잡도

O(NM)

💡틀린 이유 or 수정할 부분

처음이동거리를 어떻게 구현해야할지 몰라서 헷갈렸다. 도저히 모르겠어서 구글링 도중 현재 위치에서 이동한 위치에 한칸씩 추가하면 된다는것을 알게되었다. 이해가 잘 안가서 그림을 그려 해보니 이해가 한번에 갔다. (왜 다른분들 블로그에 ..ㅠ 설명이 없는게 너무 많ㅎ..타

💡틀린 부분 수정 or 다른풀이

• Java

package algorithms_Java02_6;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class baekjoon_2178 {
	static int N, M;
	static int arr[][];
	static boolean visit[][];
	static int [] dx = {-1, 1, 0, 0};
	static int [] dy = {0, 0, -1, 1};
		public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int [N][M];
		visit = new boolean[N][M];
		for(int i =0; i < N; i++) {
			String row = br.readLine();
			for(int j = 0; j < M; j++) {
				arr[i][j] = row.charAt(j) - '0';
			}
		}
		visit[0][0] = true;
		bfs(0,0);
		System.out.println(arr[N-1][M-1]);
	}
		public static void bfs(int x, int y) {
			Queue<int[]> que = new LinkedList<>();
			que.offer(new int[] {x, y});
			visit[x][y] = true;
			while(!que.isEmpty()) {
				int[] poll = que.poll();
				int poll_x = poll[0];
				int poll_y = poll[1];
				for(int i = 0; i < 4; i++) {
					int next_x = dx[i] + poll_x;
					int next_y = dy[i] + poll_y;
					if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < M && !visit[next_x][next_y] && arr[next_x][next_y] == 1) {
						que.offer(new int[] {next_x,next_y});
						visit[next_x][next_y] = true; // 체크
						arr[next_x][next_y] = arr[poll_x][poll_y] + 1; // 각 배열에 이동한 거리를 추가
					}
				}
			}
		}
}

💡느낀점 or 기억할 정보

처음 DFS로 해야하나 했지만 최소 거리를 보고 BFS로 풀어야 된다는것을 알게됬다. 두 알고리즘 중 어떤 알고리즘을 선택해 풀어야하는지 고민이 되는거 같다.