2178번 미로탐색

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

2178번은 완전탐색 문제이고 BFS로 문제를 푸는 것이 가장 효율적이다.
사실 BFS 개념은 잘 알고 있지만, 구현을 안해본지가 오래되서 막상 오랜만에 구현을 하려니 많이 헤맸다.

외부 IDE에서는 문제없이 결과를 잘 출력했는데, 백준 사이트에서 제출하기만 누르면 메모리초과..... 메모리 어떻게 효율적으로 쓰는건데...

결국 검색을 통해서 문제를 해결하긴 했는데, 알고보니 방문처리하는 시점이 중요하다고 한다.
방문과 동시에 방문처리를 했어야했는데, 나는 방문 후 다음 루프에서 방문처리를 했기 때문에, 이미 방문한 곳도 다시한번 방문하게되는 메모리 비효율적인 코딩을 했기 때문이다. 아마 더 큰 데이터가 들어왔다면, 시간초과 까지 났을지도 모르겠다. 아래에 코드는 올바르게 수정된 코드이다. 어쨌든 오늘도 또하나의 삽질을 마치고 문제를 풀어제꼈다.

import java.util.*;
import java.io.*;

class Main{
    static int[][] graph;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int n;
    static int m;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] st = br.readLine().split(" ");
        
        n = Integer.parseInt(st[0]);
        m = Integer.parseInt(st[1]);
        
        //그래프 초기화
        graph = new int[n][m];
        for(int i=0; i<n; i++){
            String[] temp = br.readLine().split("");
            for(int j=0; j<m; j++){
                graph[i][j] = Integer.parseInt(temp[j]);
            }
        }
        //n,m 좌표까지 갈 수 있는 가장 짧은거리를 찾기위해서는
        //완전 탐색중에서도 너비우선 탐색이 유리하다.
        //너비우선 탐색은 노드를 거치는 수에 따라 단계적으로 탐색하기 때문이다.
        //아래 예시는 모든 노드는 시작정점에서부터 탐색한다.
        //1단계 : 노드 0개를 거쳐서 갈 수 있는 모든 경우 탐색(시작정점만 탐색)
        //2단계 : 노드 1개를 거쳐서 갈 수 있는 모든 경우 탐색(시작정점에서 연결되어있는 모든 노드 탐색)
        //3단계 : 노드 2개를 거쳐서 갈 수 있는 모든 경우 탐색(2단계에서 새로 탐색한 노드 중 연결되어 있는 모든 노드 탐색)
        //이렇게 이어 진다. 따라서 우리는 각 단계를 안다면 몇개의 노드(칸)를 거쳤는지 알 수 있다.
        
        bfs(0,0,1);
    }
    //x,y의 좌표, num은 x,y 좌표까지의 방문 회수(단계)를 의미
    static void bfs(int x, int y, int num){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x,y,num});
        graph[x][y]=0;
        while(!q.isEmpty()){
            int[] current = q.poll();
            
            if(current[0]==n-1 && current[1]==m-1){
                System.out.println(current[2]);
                return;
            }
            for(int i=0; i<4; i++){
                int nx = current[0]+dx[i];
                int ny = current[1]+dy[i];
                
                if(nx>=0 && nx < n && ny>=0 && ny < m){
                    if(graph[nx][ny]==1){
                        graph[nx][ny]=0;
                        q.offer(new int[]{nx, ny, current[2]+1});
                    }
                }
            }
        }
    }
}