문제

SWEA_1953_탈주범검거

요약

지하 터널의 맨홀 뚜껑 위치에서 시작해, 서로 연결 가능한 7종류의 파이프를 타고 이동할 때 경과 시간 $L$ 이하로 탈주범이 도달할 수 있는 모든 터널 위치(격자 칸)의 개수를 구하는 문제

접근

문제를 처음 보자마자 느낀건 각 파이프마다 상하좌우별 연결될 수 있는 파이프가 다 달라서 이 조합을 먼저 선언해둬야겠다 생각했다.
그리고 시작 위치부터 bfs로 돌리면서 $L$까지 돌리고, 그때 앞서 선언한 상하좌우별 연결되는 파이프가 있다면 answer값을 1씩 올리면서 최종적으로 answer값을 반환하면 될 것이라 생각하고 접근했다.

알고리즘

1. 전체 2차원 배열을 하나 만든다.
2. 값들을 기본 값(파이프 위치)에 맞게 초기화한다.
3. dr, dc를 만들어 상하좌우 탐색을 하게 만든다.
4. 기본 위치를 시작으로 visited 배열로 방문 여부를 체크하면서, $L$ 너비까지 상하좌우 bfs 탐색을 돌린다.
5. 현재 내 위치의 파이프와 상하좌우 파이프의 조합을 확인하며 연결된다면 answer값을 증가시키고 visited 위치를 true로 변경한다.
6. 최종적으로 answer값을 출력한다.

제출 코드

import java.util.*;
import java.io.*;
 
public class Solution {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int[][] land;
    static boolean[][] visited;
    // 파이프의 각 방향이 뚫려있을 때, 연결할 수 있는 파이프들
    static int[] up = {1,2,5,6};
    static int[] down = {1,2,4,7};
    static int[] left = {1,3,4,5};
    static int[] right = {1,3,6,7};
    static int N;
    static int M;
     
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
         
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken())+1;
            M = Integer.parseInt(st.nextToken())+1;
            int R = Integer.parseInt(st.nextToken())+1; // 시작 위치 x
            int C = Integer.parseInt(st.nextToken())+1; // 시작 위치 y
            int L = Integer.parseInt(st.nextToken()); // 소요 시간
             
            land = new int[N][M]; // 테두리를 한바퀴 두름
            visited = new boolean[N][M]; // 해당 파이프 방문 여부 체크
            // 땅 생성
            for (int i = 1; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j < M; j++) {
                    land[i][j] = Integer.parseInt(st.nextToken());
                }
            }
             
            int res = bfs(L, R, C);
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        }
        System.out.print(sb.toString());
    }
     
    public static int bfs(int breadth, int x, int y) {
        int res = 0;
        Queue<Node> q = new ArrayDeque<>();
        // 시작 파이프 집어 넣음
        q.offer(new Node(x, y, land[x][y]));
        visited[x][y] = true;
        res += 1;
        int time = 1;
         
        while(!q.isEmpty()) {
            // 목표만큼 너비 탐색 했으면 종료
            if (time >= breadth) break;
             
            int size = q.size();
            for (int s = 0; s < size; s++) {
                Node n = q.poll();
                // 현재 노드의 사방면을 조사
                for (int i = 0; i < 4; i++) {
                    // 지금 노드의 파이프와 사방면 각각의 파이프가 매칭이 가능한지
                    int nr = n.x+dr[i];
                    int nc = n.y+dc[i];
                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
                        continue;
                    }
                    // 연결된 위치의 파이프
                    int nextPipe = land[nr][nc];
                    if (isConnected(n.pipe, nextPipe, i) && !visited[nr][nc]) {
                        q.offer(new Node(nr, nc, land[nr][nc]));
                        visited[nr][nc] = true;
                        res+=1;
                    }
                }   
            }
            time++;
        }
         
        return res;
    }
     
    public static boolean isConnected(int pipeA, int pipeB, int direct) {
        if (pipeB == 0) return false;
         
        if (pipeA == 1) {
            // 상
            if (direct == 0) {
                for (int i : up) {
                    if (i == pipeB) return true;
                }
            }
            // 하
            else if (direct == 1) {
                for (int i : down) {
                    if (i == pipeB) return true;
                }
            }
            // 좌
            else if (direct == 2) {
                for (int i : left) {
                    if (i == pipeB) return true;
                }
            }
            // 우
            else {
                for (int i : right) {
                    if (i == pipeB) return true;
                }
            }
        }
        else if (pipeA == 2) {
            // 상
            if (direct == 0) {
                for (int i : up) {
                    if (i == pipeB) return true;
                }
            }
            // 하
            if (direct == 1) {
                for (int i : down) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 3) {
            // 좌
            if (direct == 2) {
                for (int i : left) {
                    if (i == pipeB) return true;
                }
            }
            // 우
            if (direct == 3) {
                for (int i : right) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 4) {
            // 상
            if (direct == 0) {
                for (int i : up) {
                    if (i == pipeB) return true;
                }
            }
            // 우
            if (direct == 3) {
                for (int i : right) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 5) {
            // 하
            if (direct == 1) {
                for (int i : down) {
                    if (i == pipeB) return true;
                }
            }
            // 우
            if (direct == 3) {
                for (int i : right) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 6) {
            // 하
            if (direct == 1) {
                for (int i : down) {
                    if (i == pipeB) return true;
                }
            }
            // 좌
            if (direct == 2) {
                for (int i : left) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 7) {
            // 상
            if (direct == 0) {
                for (int i : up) {
                    if (i == pipeB) return true;
                }
            }
            // 좌
            if (direct == 2) {
                for (int i : left) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        return false;
    }
     
    public static class Node {
        int x;
        int y;
        int pipe;
         
        public Node(int x, int y, int pipe) {
            this.x = x;
            this.y = y;
            this.pipe = pipe;
        }
    }
}

어려웠던 점

bfs를 짜면서, 특정 시간($L$)이 되었을 때, 종료시키는 걸 구현하는게 bfs 알고리즘 구현하는게 익숙하지 않아서 어려웠다.

• 시간 제한이나 거리 제한이 있는 bfs의 경우 q.size()로 레벨 순회를 사용하거나 bfs로 넘기는 값에 time이나 length와 같이 변수를 만들어 관리해야한다!

또한 처음에 방문 여부를 체크하지 않고 그냥 돌려서 무한루프에 빠지기도 했다.
이미 연결되었던 부분에 대해선 visited 체크를 통해 다시 방문하지 않도록 처리하는게 중요하다!

또 내 위치의 파이프가 1번 파이프인 경우, 어차피 연결된다 생각하고, true를 반환했는데, 1번 파이프와 연결되지 않는 파이프들도 있다는걸 뒤늦게 파악했다. 이를 파악하는데 시간을 소모했다..

추가로...) pipe끼리 연결되는지에 대한 여부를 모두 하드코딩으로 박았는데, 이게 맞는지 잘 모르겠다...
➡️비트 마스킹을 사용하거나, 2차원 배열로 파이프별 가능한 여부를 저장해두는 방식으로 구현하면 가능하다고 한다...
비트마스킹을 잘 모르니까, 이와 관련한 문제를 여러 문제 풀면서 익혀야한다는걸 느낀다...
(세상엔 참 배워야할게 많다...)

새롭게 알게된 점

코드를 작성할 때, step by step으로 잘 구현되고 있는지 확인하는 것이 중요한 것임을 또 깨달았다...
다 만들고 돌리니 어디서부터 잘못된건지 찾기가 너무 어렵다!!