백준 2178번 - 미로탐색 / Java

문제: https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

문제 설명

문제

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

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

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

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

입력

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

출력

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

 

---

정답

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 Main {

	static int n;
	static int m;
	static int[][] map;
	static boolean[][] visited;

	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());// 열

		map = new int[n][m]; // 미로 지도
		visited = new boolean[n][m]; // 방문 여부
		visited[0][0] = true;

		for (int i = 0; i < n; i++) { // 지도 생성
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for (int j = 0; j < m; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}

		search(0, 0);
		System.out.println(map[n - 1][m - 1]);
	}

	public static void search(int x, int y) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] { x, y });

		// 이동 할 수 있는 가지 수, 동서남북
		int[] dx = { 1, 0, -1, 0 };
		int[] dy = { 0, 1, 0, -1 };

		while (!queue.isEmpty()) { // 큐에 들어간 좌표 탐색이 모두 끝날 때까지 반복
			int[] xy = queue.poll();

			for (int i = 0; i < 4; i++) { // 동, 서, 남, 북 탐색
				int nextX = xy[0] + dx[i];
				int nextY = xy[1] + dy[i];

				// 다음 지점이 미로를 벗어나거나, 벽이거나, 이미 탐색을 한 좌표이면 무시
				if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || visited[nextX][nextY]
						|| map[nextX][nextY] == 0) {
					continue;
				}

				// 다음 탐색 지점을 큐에 추가
				queue.add(new int[] { nextX, nextY });

				// 다음 탐색 지점 탐색처리
				visited[nextX][nextY] = true;

				// 다음 탐색 지점의 비용을 현재 좌표 + 1 로 변경
				map[nextX][nextY] = map[xy[0]][xy[1]] + 1;
			}
		}
	}
}

 

풀이

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int n;
	static int m;
	static int[][] arr;
	static boolean[][] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt(); // 행
		m = sc.nextInt(); // 열

		arr = new int[n][m]; // 미로 지도
		visited = new boolean[n][m]; // 방문 여부

		for (int i = 0; i < n; i++) { // 지도 생성
			char[] chaArr = sc.next().toCharArray();
			for (int j = 0; j < m; j++) {
				arr[i][j] = chaArr[j] - '0';
			}
		}

		search(0, 0);
		System.out.println(arr[n - 1][m - 1]);
	}

	public static void search(int x, int y) {
		Queue<XY> queue = new LinkedList<XY>();
		queue.add(new XY(x, y));

		// 이동 할 수 있는 가지 수, 동서남북
		int[] dx = { 1, 0, -1, 0 };
		int[] dy = { 0, 1, 0, -1 };

		while (!queue.isEmpty()) { // 큐에 들어간 좌표 탐색이 모두 끝날 때까지 반복
			XY xy = queue.poll();

			// 현재 좌표 탐색처리
			visited[xy.x][xy.y] = true;

			for (int i = 0; i < 4; i++) { // 동, 서, 남, 북 탐색
				int nextX = xy.x + dx[i];
				int nextY = xy.y + dy[i];

				// 다음 지점이 미로를 벗어나거나, 벽이거나, 이미 탐색을 한 좌표이면 무시
				if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || arr[nextX][nextY] == 0
						|| visited[nextX][nextY]) {
					continue;
				}

				// 다음 탐색 지점을 큐에 추가
				queue.add(new XY(nextX, nextY));

				//
				arr[nextX][nextY] = arr[xy.x][xy.y] + 1;
			}
		}
	}
}

class XY { // 좌표 저장
	int x;
	int y;

	public XY(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

 데이터를 전부 받고, (0, 0) 부터 (n - 1, m - 1)까지 BFS로 탐색하는 식으로 구현했습니다. XY라는 클래스를 만들어서 순서대로 큐에 넣어서 탐색하도록 했는데, 메모리 초과가 나서 다른 해결 방법을 찾아야 할 것 같습니다. 

 제 예상으로는 21번 줄에 있는 지도 생성 부분에서 문제가 생기는 것 같습니다.

 

for (int i = 0; i < n; i++) { // 지도 생성
  String str = sc.next();
  for (int j = 0; j < m; j++) {
 	 arr[i][j] = str.charAt(j) - '0';
  }
}

 지도 생성 부분을 이렇게 바꿔도 메모리 초과가 납니다. 다른 곳에도 문제가 있는 것 같습니다.

 

 구글링하면서 찾아보니 탐색처리하는 부분이 문제였습니다.

public static void search(int x, int y) {
    Queue<int[]> queue = new LinkedList<int[]>();
    queue.add(new int[] { x, y });

    // 이동 할 수 있는 가지 수, 동서남북
    int[] dx = { 1, 0, -1, 0 };
    int[] dy = { 0, 1, 0, -1 };

    while (!queue.isEmpty()) { // 큐에 들어간 좌표 탐색이 모두 끝날 때까지 반복
        int[] xy = queue.poll();

        for (int i = 0; i < 4; i++) { // 동, 서, 남, 북 탐색
            int nextX = xy[0] + dx[i];
            int nextY = xy[1] + dy[i];

            // 다음 지점이 미로를 벗어나거나, 벽이거나, 이미 탐색을 한 좌표이면 무시
            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || visited[nextX][nextY]
                    || map[nextX][nextY] == 0) {
                continue;
            }

            // 다음 탐색 지점을 큐에 추가
            queue.add(new int[] { nextX, nextY });

            // 다음 탐색 지점 탐색처리
            visited[nextX][nextY] = true;

            // 다음 탐색 지점의 비용을 현재 좌표 + 1 로 변경
            map[nextX][nextY] = map[xy[0]][xy[1]] + 1;
        }
    }
}

 기존 코드에서는 탐색처리를 해당 좌표를 방문할 때 했는데, 그러다 보니 해당 좌표를 직접 방문할 때까지 인근 좌표를 탐색할 때 큐에 추가되는 부분때문에 메모리 초과가 발생한 것으로 보입니다. 해결방법은 해당 좌표를 방문할 때 방문처리를 하는 것이 아닌, 큐에 추가할 때 방문처리를 하는 것입니다.