코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int m, n;
    static int[] dy = { -1, 0, 1, 0 };
    static int[] dx = { 0, -1, 0, 1 };
    static int[][] miroData;
    static boolean[][] discover;

    public static void bfs(){
        Queue<int[]> list = new LinkedList<>();
        list.offer(new int[]{ 0, 0});
        while (!list.isEmpty()){
            int[] miro = list.poll();
            int y = miro[0];
            int x = miro[1];
            int count = miroData[y][x];``

            for (int i = 0; i < 4; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];

                if(nextY < 0 || nextY >= m || nextX < 0 || nextX >= n){
                    continue;
                }
                int isGo = miroData[nextY][nextX];
                if(isGo == 0 || discover[nextY][nextX] == true){
                    continue;
                }
                miroData[nextY][nextX] = count + 1;
                discover[nextY][nextX] = true;
                list.offer(new int[] {nextY, nextX});
            }
        }
    }

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        miroData = new int[m][n];
        discover = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            String data = st.nextToken();
            for (int j = 0; j < n; j++) {
                miroData[i][j] = data.charAt(j) - 48;
            }
        }
        discover[0][0] = true;
        bfs();
        System.out.println(miroData[m-1][n-1]);
    }
}

복기

메모리 초과 폭탄

메모리 초과 발생 이유

• 결론 부터 말하자면 queue의 사이즈가 발생 원인

메모리 초과 bfs 코드

    public static void bfs(){
        Queue<int[]> list = new LinkedList<>();
        list.offer(new int[]{ 0, 0});
        while (!list.isEmpty()){
            int[] miro = list.poll();
            int y = miro[0];
            int x = miro[1];
            int count = miroData[y][x];
            discover[y][x] = true;

            for (int i = 0; i < 4; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];

                if(nextY < 0 || nextY >= m || nextX < 0 || nextX >= n){
                    continue;
                }
                int isGo = miroData[nextY][nextX];
                if(isGo == 0 || discover[nextY][nextX] == true){
                    continue;
                }
                miroData[nextY][nextX] = count + 1;
                list.offer(new int[] {nextY, nextX});
            }
        }
    }

통과된 bfs 코드

    public static void bfs(){
        Queue<int[]> list = new LinkedList<>();
        list.offer(new int[]{ 0, 0});
        while (!list.isEmpty()){
            int[] miro = list.poll();
            int y = miro[0];
            int x = miro[1];
            int count = miroData[y][x];

            for (int i = 0; i < 4; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];

                if(nextY < 0 || nextY >= m || nextX < 0 || nextX >= n){
                    continue;
                }
                int isGo = miroData[nextY][nextX];
                if(isGo == 0 || discover[nextY][nextX] == true){
                    continue;
                }
                miroData[nextY][nextX] = count + 1;
                discover[nextY][nextX] = true; // 바뀐건 요 코드
                list.offer(new int[] {nextY, nextX});
            }
        }
    }

메모리 초과 확인 case

7 7
1111111
1111111
1111111
1111111
1111111
1111111
1111111

queue 사이즈 확인

• 통과된 queue사이즈
  
• 메모리초과 queue 사이즈
  

결론

• queue에 중복 값이 없어야 메모리 초과가 안됨.

public static void bfs(){
        Queue<int[]> list = new LinkedList<>();
        ...
        while (!list.isEmpty()){
            int[] miro = list.poll();
            int y = miro[0];
            int x = miro[1];

            for (int i = 0; i < 4; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];

                ...
                if( ... || discover[nextY][nextX] == true){
                    continue;
                }
                
                discover[nextY][nextX] = true;
                list.offer(new int[] {nextY, nextX});
            }
        }
    }