[백준] 27453번 - 귀엽기만 한게 아닌 한별 양

문제

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

27453번: 귀엽기만 한 게 아닌 한별 양

 

입력

 

출력

---

알고리즘

너비 우선 탐색(BFS)

 

꽤 푸는데 고생을 했던 문제였다. 근데 굉장히 아이디어가 재밌는 BFS 문제!!

 

최근 지나온 3칸의 개수가 k개를 넘는지 확인하면서 최단 거리를 구하는 것이므로 BFS를 돌리면 된다. 여기서 중요한 것이, 최근 지나온 3칸만 보면 되는 것이므로 이미 왔던 칸이라도, 돌아서 오면 지나갈 수 있는 경우가 생긴다는 것이다.

6 6 4
S1113X
33323X
11211X
13311X
1XXXXX
11111H

예를 들어 예제 1번과 같이 입력이 들어왔다고 생각해보자. 원래 그냥 BFS를 돌리

딱 이 순간에서 왼쪽 2를 밟고 가야 지나갈 수 있는데, (다른 길은 다 3으로 되있어서 이걸 밟으면 무조건 k값인 4를 넘어가기 때문임) 지금 딱 저 순간에서 2를 밟을 경우, 최근 지나온 칸이 2 + 1 + 2 = 5가 되버려서 지나갈 수 없다. 하지만? 돌아간다면 어떻게 될까?

 

그림판으로 그려서 형편 없긴 한데, 1이 4개 모여있는 구역을 한바퀴 돌아서 오면 1 + 1 + 2 = 4로 통과가 가능해지고 목적지에 도달이 가능해진다. 여기에서 주목해야될 부분은, 이러면 방문했던 칸을 또 방문하도록 설계해야된다. 하지만, 그렇다고 visited를 아예 없어버리면 무조건 메모리가 터지고, 무한 루프를 도니깐 그럼 또 안된다. 그래서 여기서 visited를 어떻게 설계할까에 대해서 고민해야된다.

 

바로 위에 그림처럼, 어느 방향에서 들어온건지를 따지는 요소를 visited를 추가해주면 된다. 예를 들어, 앞서 말한 저 1칸에 도달하기 위해서 어느 방향으로 들어왔는지를 visited에 반영하는 것이다. visited[2][3][1] 이런식이면 왼쪽 방향에서 들어온 (2,3)은 방문처리를 해준다 이런 느낌으로 말이다. 이렇게 4방향에 대해서 visited 처리를 해주면, 같은 방향에서 들어온 값은 또다시 같은 행동을 반복할 것이니깐 무시해주고, 다른 방향에서 들어온 값은 또 값이 다를 것이니 그거는 그거대로 계산해줄 수 있다. 그리고 큐에 넣을땐 좌표, 이동한 거리, 들어온 방향 이렇게 4개 넣어주고 BFS를 돌리면 된다.

 

또한, 문제 조건에서 바로 전 칸으로는 바로 이동할 수 없다는 조건이 있으므로, 방향 백터 순서를 잘 설계해서 전 방향이랑 랑 정반대로 향하는지 체크해주고 이를 무시해주면 된다.

 

설명을 좀 어렵게 써놨는데, 들어오는 방향 요소를 visited에 추가해준다를 생각하고 밑에 코드를 보면 이해가 갈 것이다.  

---

코드

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

public class Main {
    static int[][] board;
    static boolean[][][] visited;
    static int n,m,k;
    static int end_x, end_y;

    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());
        k = Integer.parseInt(st.nextToken());


        int start_x = -1, start_y = -1;
        end_x = -1;
        end_y = -1;
        board = new int[n][m];

        for(int i = 0; i<n; i++){
            String tmp = br.readLine();
            for(int j = 0; j<m; j++){
                char cur = tmp.charAt(j);
                if(cur == 'S'){
                    board[i][j] = 0;
                    start_x = i;
                    start_y = j;
                }
                else if(cur == 'H'){
                    board[i][j] = 0;
                    end_x = i;
                    end_y = j;
                }
                else if(cur == 'X') board[i][j] = -1;
                else board[i][j] = cur - '0';
            }
        }

        visited = new boolean[n][m][4];
        System.out.println(bfs(start_x, start_y));
    }

    public static int bfs(int a, int b){
        Queue<int[]> queue = new LinkedList<>();
        //x좌표, y좌표, 이동 거리, 들어온 방향
        queue.add(new int[]{a,b,0,-1});
        //처음 지점으로는 다시는 못들어오도록 설정
        for(int i = 0; i<4; i++) visited[a][b][i] = true;

        int[] dirx = {1,0,0,-1};
        int[] diry = {0,-1,1,0};

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            int dist = cur[2];
            int prev = cur[3];

            if(x == end_x && y == end_y) return dist;

            for(int i = 0; i<4; i++){
                int nx = x + dirx[i];
                int ny = y + diry[i];

                if(nx<0 || ny<0 || nx>=n || ny>=m || visited[nx][ny][i] || board[nx][ny]<0) continue;
                //다음칸 역경이 k개 이상이면 볼 필요도 없음
                //또한, 문제 조건 중에서 바로 이전 칸으로 돌아가지 못한다는 조건이 있음. 우리가 방향백터를 3-prev한거를 prev의 반대로 설정해둠
                //따라서 prev와 3-prev랑 같다면 바로 이전칸으로 돌아가려고 시도하는거니깐 스킵
                if(board[nx][ny]>k || i == (3-prev)) continue;
                //이전칸 + 현재칸 + 다음칸이 k를 넘는지 확인.
                if(prev != -1 && ((board[x-dirx[prev]][y-diry[prev]] + board[x][y] + board[nx][ny]) > k))continue;
                visited[nx][ny][i] = true;
                queue.add(new int[]{nx, ny, dist+1, i});
            }
        }

        return -1;
    }
}