[자바] 백준 18818 - Iguana Instructions (boj java)

문제 : boj18818

 

  bfs로 진행하되, 거리가 증가되는 기준이 한 방향으로 일직선으로 장애물을 만나기 전까지 모두가 동일한 거리를 가진다.그리고, 한 방향으로 일직선으로 진행하면서 만난 모든 지점을 큐에 추가하면서 풀어주면 된다. 예를들어 예제 입력 2를 봐보자.

5
.....
.###.
.....
.####
.....

 

  우선 시작점에서 bfs를 진행한 결과에 따른 각 지점의 거리는 다음과 같다.

 

  그리고 현재 거리가 '1'인 지점은 모두 큐에 추가된 상태이다. 맨 윗줄만 봤을 때, 2,3,4번째 칸들은 더이상 진행할 곳이 없으므로 그대로 무시된다. 맨 윗줄 5번째칸에서 진행한 결과는 다음과 같을 것이다.

 

  다음으로 좌측줄 정중앙에서 진행한 결과는 다음과 같다.

  

  마지막으로 맨 아래줄 좌측에서 진행한 결과는 다음과 같다.

 

  이렇듯, 기존 bfs와 마찬가지로 줄 단위로 거리를 증가하면서 bfs를 진행하다가 골인 지점에 도착 시 먼저 도착한 녀석이 가장 적게 방향을 바꾼 녀석일 것이므로 그대로 출력해주면 된다.

 

  다만 주의점은 방문체크를 그냥 해주면 안되고, 4방향으로 해줘야 한다. v[i][j][d]는 (i, j) 위치로 방향 d에서 들어온 경우를 의미한다. 왜냐하면 기존 bfs와 다르게 일직선으로 진행되므로, 방향으로 체크를 해주지 않을 경우 최소 루트를 찾을 수 없기 때문이다. 이에 대한 이해는 블로그에 작성한 bfs 설명 글(링크)에서 맨 아래쪽에 써둔 '방문체크에 대해 좀 더 써봄' 부분을 읽어보자.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    class Pos {
        int r, c, dist;
        public Pos(int r, int c, int dist) {
            this.r = r;
            this.c = c;
            this.dist = dist;
        }
    }
    int[] dr = {1, 0, 0, -1};
    int[] dc = {0, 1, -1, 0};
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        boolean[][][] v = new boolean[n][n][4];
        for (int i = 0; i < n; i++) {
            String row = br.readLine();
            for (int j = 0; j < n; j++) {
                for (int d = 0; d < 4; d++) {
                    v[i][j][d] = row.charAt(j)=='.'?false:true;
                }
            }
        }
        Queue<Pos> q = new ArrayDeque<>();
        q.add(new Pos(0, 0, 0));
        for (int d = 0; d < 4; d++) {
            v[0][0][d] = true;
        }

        while (!q.isEmpty()) {
            Pos cur = q.poll();
            if (cur.r==n-1 && cur.c==n-1) {
                System.out.println(cur.dist);
                return;
            }
            for (int d = 0; d < 4; d++) {
                int nr = cur.r + dr[d];
                int nc = cur.c + dc[d];
                while (nr>=0&&nr<n&&nc>=0&&nc<n&&!v[nr][nc][d]) {
                    v[nr][nc][d] = true;
                    q.add(new Pos(nr, nc, cur.dist+1));
                    nr+=dr[d];
                    nc+=dc[d];
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}