본문 바로가기
알고리즘/BFS

[백준] 벽 부수고 이동하기/자바

by 순원이 2024. 5. 7.

문제         

레벨: G3
알고리즘: BFS 
풀이시간:  1시간 20분
힌트 참조 유무: 유

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

1 번째 시도   

  • 벽을 언제 뽀갤 건지 한 번에 알 수 있나?
    • NO
  • 근데 왜 dfs가 아니고 bfs 인가?
    • dfs는 최단 경로를 찾는 것이 아니라 끝까지 탐색해서 경로를 찾는 것이기 때문에 첫 번째 도착한 것이 최단경로임을 보장하지 않는다. 최단 경로 찾기에 bfs가 적합하다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;


public class Main {

    static int[] xx = new int[]{1, 0, 0, -1};
    static int[] yy = new int[]{0, 1, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int r = Integer.parseInt(s[0]);
        int c = Integer.parseInt(s[1]);
        int answer = -1;

        //배열 초기화
        int[][] arr = new int[r][c];
        for (int i = 0; i < r; i++) {
            String[] s2 = br.readLine().split("");
            for (int j = 0; j < c; j++) {
                arr[i][j] = Integer.parseInt(s2[j]);
            }
        }

        Queue<Position> q = new LinkedList<Position>();
        q.add(new Position(0, 0, 0, 0));
        while (!q.isEmpty()) {
            System.out.println("시작");
            Position p = q.poll();
            int x = p.x;
            int y = p.y;
            int breakCnt = p.breakCnt;
            int cnt = p.cnt;
            System.out.println("x: " + x+" y: " + y + " breakCnt: " + breakCnt + " cnt: " + cnt);
            if (breakCnt == 2) {
                System.out.println("countiue");
                continue;
            }
            if (x == r - 1 && y == c - 1) {
                answer = cnt;
                System.out.println("정답 도출");
            }
            for (int i = 0; i < 4; i++) {
                if (x + xx[i] >= 0 && x + xx[i] < c && y + yy[i] >= 0 && y + yy[i] < r) {
                    if (arr[y + yy[i]][x + xx[i]] == 1) {
                        q.add(new Position(x + xx[i], y + yy[i], breakCnt + 1, cnt+1));
                    } else {
                        q.add(new Position(x + xx[i], y + yy[i], breakCnt, cnt+1));
                    }
                    System.out.println("for문 돌아갑니다");
                }

            }
        }

        System.out.println(answer);
    }

    public static class Position {
        int x;
        int y;
        int breakCnt;
        int cnt;

        public Position(int x, int y, int breakCnt, int cnt) {
            this.x = x;
            this.y = y;
            this.breakCnt = breakCnt;
            this.cnt = cnt;
        }
    }
}
  • sout를 찍어봐서 디버깅을 해보았지만 4방향으로 큐에 집어넣기 때문에 지나왔던 길도 큐에 들어간다. 그러기 때문에 첫번째 예제를 입력하였을 때 무한반복(?)이 일어나는 듯 싶다.
    • 그래서 visited[][] 배열과 우선순위 큐를 사용하였다.

2 번째 시도  

 

알고리즘 이해를 돕기 위해 sout도 찍어봤습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;


public class Main {

    static int[] xx = new int[]{1, 0, 0, -1};
    static int[] yy = new int[]{0, 1, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int r = Integer.parseInt(s[0]);
        int c = Integer.parseInt(s[1]);
        int answer = -1;

        //배열 초기화
        int[][] arr = new int[r][c];
        for (int i = 0; i < r; i++) {
            String[] s2 = br.readLine().split("");
            for (int j = 0; j < c; j++) {
                arr[i][j] = Integer.parseInt(s2[j]);
            }
        }

        PriorityQueue<Position> q = new PriorityQueue<Position>();
        boolean[][] visited = new boolean[r][c];
        q.add(new Position(0, 0, 0, 1));
        while (!q.isEmpty()) {
            System.out.println();
            System.out.println("while 새시작");


            Position p = q.poll();
            int x = p.x;
            int y = p.y;
            int breakCnt = p.breakCnt;
            int cnt = p.cnt;
            visited[y][x] = true;
            System.out.println("현재 positon   x: " + x+" y: " + y + " breakCnt: " + breakCnt + " cnt: " + cnt);
            if (breakCnt == 2) {
                System.out.println("countiue");
                visited[y][x] = false;
                continue;
            }
            if (x == c - 1 && y == r - 1) {
                answer = cnt;
                System.out.println("정답 도출");
                break;
            }
            for (int i = 0; i < 4; i++) {
                if (x + xx[i] >= 0 && x + xx[i] < c && y + yy[i] >= 0 && y + yy[i] < r && !visited[y+yy[i]][x+xx[i]]) {
                    if (arr[y + yy[i]][x + xx[i]] == 1) {
                        q.add(new Position(x + xx[i], y + yy[i], breakCnt + 1, cnt+1));
                    } else {
                        q.add(new Position(x + xx[i], y + yy[i], breakCnt, cnt+1));
                    }
                    System.out.println(i + "번째 for문 돌아갑니다");
                }
            }
            System.out.println("큐 안에 들어가 있는 것들:");
            for(Position o : q) {
                System.out.println("x: " + o.x+" y: " + o.y + " breakCnt: " + o.breakCnt + " cnt: " + o.cnt);
            }
        }

        System.out.println(answer);
    }

    public static class Position implements Comparable<Position> {
        int x;
        int y;
        int breakCnt;
        int cnt;

        public Position(int x, int y, int breakCnt, int cnt) {
            this.x = x;
            this.y = y;
            this.breakCnt = breakCnt;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Position p) {
            if(this.x == p.x) {
                return p.y - this.y;
            }
            if(this.y == p.y) {
                return p.x - this.x;
            }
            return p.x- this.x;
        }
    }
}

 

 

"C:\Program Files\Java\jdk-17\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\lib\idea_rt.jar=13105:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\User\Desktop\Java코드\java-pratice\out\production\java-pratice Main
6 4
0100
1110
1000
0000
0111
0000

while 새시작
현재 positon   x: 0 y: 0 breakCnt: 0 cnt: 1
0번째 for문 돌아갑니다
1번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 1 y: 0 breakCnt: 1 cnt: 2
x: 0 y: 1 breakCnt: 1 cnt: 2

while 새시작
현재 positon   x: 1 y: 0 breakCnt: 1 cnt: 2
0번째 for문 돌아갑니다
1번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 2 y: 0 breakCnt: 1 cnt: 3
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 1 y: 1 breakCnt: 2 cnt: 3

while 새시작
현재 positon   x: 2 y: 0 breakCnt: 1 cnt: 3
0번째 for문 돌아갑니다
1번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 3 y: 0 breakCnt: 1 cnt: 4
x: 2 y: 1 breakCnt: 2 cnt: 4
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 0 y: 1 breakCnt: 1 cnt: 2

while 새시작
현재 positon   x: 3 y: 0 breakCnt: 1 cnt: 4
1번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 3 y: 1 breakCnt: 1 cnt: 5
x: 2 y: 1 breakCnt: 2 cnt: 4
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 0 y: 1 breakCnt: 1 cnt: 2

while 새시작
현재 positon   x: 3 y: 1 breakCnt: 1 cnt: 5
1번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 3 y: 2 breakCnt: 1 cnt: 6
x: 2 y: 1 breakCnt: 2 cnt: 4
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 2 y: 1 breakCnt: 2 cnt: 6

while 새시작
현재 positon   x: 3 y: 2 breakCnt: 1 cnt: 6
1번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 3 y: 3 breakCnt: 1 cnt: 7
x: 2 y: 1 breakCnt: 2 cnt: 6
x: 2 y: 2 breakCnt: 1 cnt: 7
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 2 y: 1 breakCnt: 2 cnt: 4
x: 1 y: 1 breakCnt: 2 cnt: 3

while 새시작
현재 positon   x: 3 y: 3 breakCnt: 1 cnt: 7
1번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 3 y: 4 breakCnt: 2 cnt: 8
x: 2 y: 1 breakCnt: 2 cnt: 6
x: 2 y: 3 breakCnt: 1 cnt: 8
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 2 y: 1 breakCnt: 2 cnt: 4
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 2 y: 2 breakCnt: 1 cnt: 7

while 새시작
현재 positon   x: 3 y: 4 breakCnt: 2 cnt: 8
countiue

while 새시작
현재 positon   x: 2 y: 3 breakCnt: 1 cnt: 8
1번째 for문 돌아갑니다
2번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 2 y: 4 breakCnt: 2 cnt: 9
x: 2 y: 1 breakCnt: 2 cnt: 6
x: 2 y: 2 breakCnt: 1 cnt: 7
x: 1 y: 3 breakCnt: 1 cnt: 9
x: 2 y: 1 breakCnt: 2 cnt: 4
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 2 y: 2 breakCnt: 1 cnt: 9
x: 0 y: 1 breakCnt: 1 cnt: 2

while 새시작
현재 positon   x: 2 y: 4 breakCnt: 2 cnt: 9
countiue

while 새시작
현재 positon   x: 2 y: 2 breakCnt: 1 cnt: 7
2번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 2 y: 2 breakCnt: 1 cnt: 9
x: 2 y: 1 breakCnt: 2 cnt: 6
x: 2 y: 1 breakCnt: 2 cnt: 8
x: 1 y: 3 breakCnt: 1 cnt: 9
x: 2 y: 1 breakCnt: 2 cnt: 4
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 1 y: 2 breakCnt: 1 cnt: 8

while 새시작
현재 positon   x: 2 y: 2 breakCnt: 1 cnt: 9
2번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 2 y: 1 breakCnt: 2 cnt: 6
x: 2 y: 1 breakCnt: 2 cnt: 4
x: 2 y: 1 breakCnt: 2 cnt: 8
x: 2 y: 1 breakCnt: 2 cnt: 10
x: 1 y: 2 breakCnt: 1 cnt: 8
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 1 y: 3 breakCnt: 1 cnt: 9
x: 1 y: 2 breakCnt: 1 cnt: 10

while 새시작
현재 positon   x: 2 y: 1 breakCnt: 2 cnt: 6
countiue

while 새시작
현재 positon   x: 2 y: 1 breakCnt: 2 cnt: 4
countiue

while 새시작
현재 positon   x: 2 y: 1 breakCnt: 2 cnt: 10
countiue

while 새시작
현재 positon   x: 2 y: 1 breakCnt: 2 cnt: 8
countiue

while 새시작
현재 positon   x: 1 y: 3 breakCnt: 1 cnt: 9
1번째 for문 돌아갑니다
2번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 1 y: 4 breakCnt: 2 cnt: 10
x: 1 y: 2 breakCnt: 1 cnt: 8
x: 1 y: 2 breakCnt: 1 cnt: 10
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 1 y: 2 breakCnt: 1 cnt: 10
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 0 y: 3 breakCnt: 1 cnt: 10

while 새시작
현재 positon   x: 1 y: 4 breakCnt: 2 cnt: 10
countiue

while 새시작
현재 positon   x: 1 y: 2 breakCnt: 1 cnt: 8
2번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 1 y: 2 breakCnt: 1 cnt: 10
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 1 y: 2 breakCnt: 1 cnt: 10
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 0 y: 3 breakCnt: 1 cnt: 10
x: 1 y: 1 breakCnt: 2 cnt: 9
x: 0 y: 2 breakCnt: 2 cnt: 9

while 새시작
현재 positon   x: 1 y: 2 breakCnt: 1 cnt: 10
2번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 1 y: 2 breakCnt: 1 cnt: 10
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 1 y: 1 breakCnt: 2 cnt: 9
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 3 breakCnt: 1 cnt: 10
x: 0 y: 2 breakCnt: 2 cnt: 9
x: 1 y: 1 breakCnt: 2 cnt: 11
x: 0 y: 1 breakCnt: 1 cnt: 2

while 새시작
현재 positon   x: 1 y: 2 breakCnt: 1 cnt: 10
2번째 for문 돌아갑니다
3번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 1 y: 1 breakCnt: 2 cnt: 3
x: 1 y: 1 breakCnt: 2 cnt: 11
x: 1 y: 1 breakCnt: 2 cnt: 9
x: 0 y: 3 breakCnt: 1 cnt: 10
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 0 y: 2 breakCnt: 2 cnt: 9
x: 1 y: 1 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11

while 새시작
현재 positon   x: 1 y: 1 breakCnt: 2 cnt: 3
countiue

while 새시작
현재 positon   x: 1 y: 1 breakCnt: 2 cnt: 11
countiue

while 새시작
현재 positon   x: 1 y: 1 breakCnt: 2 cnt: 9
countiue

while 새시작
현재 positon   x: 1 y: 1 breakCnt: 2 cnt: 11
countiue

while 새시작
현재 positon   x: 0 y: 3 breakCnt: 1 cnt: 10
1번째 for문 돌아갑니다
2번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 0 y: 4 breakCnt: 1 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 9
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11

while 새시작
현재 positon   x: 0 y: 4 breakCnt: 1 cnt: 11
0번째 for문 돌아갑니다
1번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 1 y: 4 breakCnt: 2 cnt: 12
x: 0 y: 2 breakCnt: 2 cnt: 9
x: 0 y: 5 breakCnt: 1 cnt: 12
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11

while 새시작
현재 positon   x: 1 y: 4 breakCnt: 2 cnt: 12
countiue

while 새시작
현재 positon   x: 0 y: 5 breakCnt: 1 cnt: 12
0번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 1 y: 5 breakCnt: 1 cnt: 13
x: 0 y: 2 breakCnt: 2 cnt: 9
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11

while 새시작
현재 positon   x: 1 y: 5 breakCnt: 1 cnt: 13
0번째 for문 돌아갑니다
2번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 2 y: 5 breakCnt: 1 cnt: 14
x: 0 y: 2 breakCnt: 2 cnt: 9
x: 1 y: 4 breakCnt: 2 cnt: 14
x: 0 y: 1 breakCnt: 1 cnt: 2
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11

while 새시작
현재 positon   x: 2 y: 5 breakCnt: 1 cnt: 14
0번째 for문 돌아갑니다
2번째 for문 돌아갑니다
큐 안에 들어가 있는 것들:
x: 3 y: 5 breakCnt: 1 cnt: 15
x: 2 y: 4 breakCnt: 2 cnt: 15
x: 1 y: 4 breakCnt: 2 cnt: 14
x: 0 y: 2 breakCnt: 2 cnt: 9
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 2 breakCnt: 2 cnt: 11
x: 0 y: 1 breakCnt: 1 cnt: 2

while 새시작
현재 positon   x: 3 y: 5 breakCnt: 1 cnt: 15
정답 도출
15

Process finished with exit code 0

 

15라는 정답이 나와 성공했다고 생각했지만 제출해보니 메모리 초과가 떴다

시간이 많이 지나 다른 사람들의 코드를 참조하며 공부해 봐야겠다.

 

다른 사람 코드   

 

  • BFS로 먼저 어떠한 위치에 도달했을 때 전에 벽을 부수고 도착했을 수도 있고 안 부수고 도착했을 수도 있다. 그러나 내 코드에서는 해당 위치에 부순 경험x가 먼저 도착했으면 부순경험 o인 것이 올 수가 없다.   
  • 일단. 다른 분들은 다 큐를 썼다. 내가 우선순위큐를 내가 잘못썼다.
  • 그리고 우선순위 큐 비교정렬 기준을 잘못세웠다.
  1. BFS + 큐 사용: BFS와 일반 큐를 사용하는 경우는 주로 간선의 가중치가 동일하거나 가중치가 없는 그래프에서 사용됩니다. BFS는 시작 노드로부터 같은 거리에 있는 노드들을 순차적으로 탐색하며, 모든 간선의 가중치가 동일하면 이 방법을 사용할 때 각 노드까지의 최단 거리를 정확하게 계산할 수 있습니다. 예를 들어, 미로 찾기나 체스 보드에서 최단 이동 횟수를 계산할 때 사용됩니다.
  2. BFS + 우선순위 큐 사용: BFS를 사용할 때 우선순위 큐(주로 최소 힙을 사용)를 함께 사용하는 경우는 간선의 가중치가 다양할 때 적합합니다. 이 방법은 다익스트라 알고리즘으로 알려져 있으며, 각 단계에서 현재 노드와 연결된 노드들 중 최소 가중치를 가진 노드를 우선적으로 탐색합니다. 이를 통해 가중치가 있는 그래프에서 각 노드까지의 최단 거리를 효율적으로 계산할 수 있습니다. 주로 도로망에서의 최단 경로 계산이나 네트워크 라우팅에서 사용됩니다.
  • visited[][] = true는 큐에 뻈을 때 해주는 것이 아니라 큐에 넣기 전에 해주는 것이다.
    • 그래야 큐에 겹치는 위치가 안 들어가기 때문(어차피 미리 들어가 있던 겹친 위치가 최소 거리임을 보장하기 때문에 나중에 겹치는 위치는 췩브 안해줘도 상관없음.)

 

핵심 포인트: visted배열 응용!!

 

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, m;
    static int[][] board;
    static boolean[][][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    // 현재 위치, 벽을 부순적이 있는지, 지나간 타일의 수를 저장하는 클래스입니다.
    static class Point {
        int x;
        int y;
        boolean destroyed;
        int cnt;

        public Point(int x, int y, boolean destroyed, int cnt) {
            this.x = x;
            this.y = y;
            this.destroyed = destroyed;
            this.cnt = cnt;
        }
    }

    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());
        board = new int[n][m];
        visited = new boolean[n][m][2];

        for (int i = 0; i < n; i++) {
            char[] charArray = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                board[i][j] = Character.getNumericValue(charArray[j]);
            }
        }

        System.out.println(bfs());
    }

    public static int bfs() {
        Queue<Point> queue = new LinkedList<>();

        // 시작점을 큐에 넣습니다.
        queue.offer(new Point(0, 0, false, 1));
        visited[0][0][0] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            // 도착하면 지나간 타일 수를 반환합니다.
            if (point.x == n - 1 && point.y == m - 1) {
                return point.cnt;
            }

            for (int d = 0; d < 4; d++) {
                int newX = point.x + dx[d];
                int newY = point.y + dy[d];

                // 배열을 벗어난 경우는 넘어갑니다.
                if (newX < 0 || newX >= n || newY < 0 || newY >= m) {
                    continue;
                }

                // 벽을 부순적이 있는지 확인합니다.
                if (point.destroyed) {
                    // 벽을 부순적이 있을 때 해당 지점이 벽이 아니고, 방문한적이 없다면 큐에 정보를 넣습니다.
                    if (board[newX][newY] == 0 && !visited[newX][newY][1]) {
                        visited[newX][newY][1] = true;
                        queue.offer(new Point(newX, newY, true, point.cnt + 1));
                    }
                } else {
                    // 해당 위치가 벽인지 확인합니다.
                    if (board[newX][newY] == 1) {
                        // 벽이라면 벽을 부수고 큐에 값을 넣습니다.
                        visited[newX][newY][1] = true;
                        queue.offer(new Point(newX, newY, true, point.cnt + 1));
                    } else if (!visited[newX][newY][0]){
                        // 벽이 아니고 방문한적이 없다면 큐에 값을 넣습니다.
                        visited[newX][newY][0] = true;
                        queue.offer(new Point(newX, newY, false, point.cnt + 1));
                    }
                }
            }
        }

        return -1;
    }
}

출처: https://ssshane.tistory.com/22

 

저작자표시

'알고리즘 > BFS' 카테고리의 다른 글

[백준 13460] 구슬 탈출2 / 자바 / BFS  (1) 2024.07.03
[백준] 아기상어 / 자바  (0) 2024.05.25
[백준] 토마토/자바  (0) 2024.05.12
항해99 26일차 TIl( 단어 변환 / 프로그래머스)  (0) 2024.04.23
항해 99 25일차 TIL( 게임 맵 최단거리 / 프로그래머스)  (0) 2024.04.22

관련글

티스토리툴바