백준 2178번: 미로 탐색

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

 

그래프 이론인 것같았으나 DFS인지, BFS인지는 감을 못잡고 있었다.

백준 알고리즘 분류로 BFS인 것을 확인하고 문제를 풀었다.

 

일단 띄어쓰기 없이 입력이 되어서 맨 처음에는 toCharArray()메소드를 썼으나,

마지막에 코드를 수정하면서 그냥 CharAt으로 입력받았다.

 

또한 미로를 2차원 배열로 입력받았는데, 

열과 행을 끝에 2개씩 넣어주는 것으로 일종의 벽을 만들어주었다.

 

BFS를 구현할 때는 큐에 시작할 좌표를 입력받아주고 시작했는데,

이때 좌표는 2점을 입력받을 수 없으니까, 0부터 (N * M) 사이의 숫자로 정해주어서 사용했다.

 

그 뒤에는 큐에  현재 사이즈만큼 루프를 돌리면서 그래프를 탐색하고

현재 그래프와 이어져 있는 그래프가 '1'이면 탐색하도록 큐에 넣어주었다.

그리고 마지막으로 큐가 방문했음을 확인해주었는데 이게 실수였다.

 

이 뒤로 계속 메모리 제한이 떠서 실패했는데,

앞서 말했듯이 방문을 확인하는 것을 맨 뒤에 해주어서 그런 것이었다.

방문 확인을 루프의 마지막에서 1개만 해주는 것보다

큐에 탐색할 그래프를 넣으면서 동시에 방문 확인을 하는 것이

중복으로 탐색할 여지를 없애주어 메모리 제한을 줄여주었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    char[][] maze = new char[N + 2][M + 2];
    for (int i = 1; i < N + 1; i++) {
      String str = br.readLine();
      for (int j = 1; j < M + 1; j++) {
        maze[i][j] = str.charAt(j - 1);
      }
    }

    //BFS
    Queue<Integer> srchQueue = new LinkedList<>(); //Index
    srchQueue.offer(M); // (1, 0) ~ N, M
    maze[1][1] = '0';
    int RES = 0;

    Label: while (true) {
      RES++;

      int sz = srchQueue.size();
      for (int i = 0; i < sz; i++) {
        int index = srchQueue.poll();
        int x = index / M;
        int y = index % M + 1; //(1, 1)
        if (x == N && y == M) break Label;

        if (maze[x][y + 1] == '1') {
          srchQueue.offer(index + 1);
          maze[x][y + 1] = '0';
        }

        if (maze[x][y - 1] == '1') {
          srchQueue.offer(index - 1);
          maze[x][y - 1] = '0';
        }

        if (maze[x + 1][y] == '1') {
          srchQueue.offer(index + M);
          maze[x + 1][y] = '0';
        }

        if (maze[x - 1][y] == '1') {
          srchQueue.offer(index - M);
          maze[x - 1][y] = '0';
        }
      }
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(RES + "");
    bw.flush();
    bw.close();
  }
}