[SWEA 1953번] 탈주범 검거 :: 늦깎이 IT

[SWEA 1953. [모의 SW 역량테스트] 탈주범 검거 URL]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE

이번 문제는 쉬운 BFS문제이지만, 현재 칸에서 다음 칸으로 넘어갈 수 있는지에 대한 조건이 많다.

아래 그림을 보자.

현재 방문한 파이프가 1번이라고 가정해보자. 그럼 1번 파이프에서 방향에 따라 다음 파이프로 이동할 수 있는지,

없는지가 결정된다. 현재 파이프가 1번이고 이동 방향이 동쪽이라고 할 때, 1번 파이프에서 이동할 수 있는 다음

파이프는 1번, 3번, 6번, 7번 파이프가 된다.

이처럼, 현재 파이프와 이동 방향에 따라 이동할 수 있는 다음 파이프인지 확인해주면서 탐색을 진행하면 된다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.concurrent.LinkedBlockingDeque;
 
public class Solution {
 
    public static int N, M, R, C, L, tCase, ans;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[] dirX = new int[] { 0, 0, 1, -1 }; // 동서남북
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= tCase; t++) {
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());
 
            ans = 0;
            map = new int[N][M];
            visited = new boolean[N][M];
 
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            bfs();
            System.out.println("#" + t + " " + ans);
        }
    }
 
    public static void bfs() {
 
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(R, C, 0));
        visited[R][C] = true;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int cnt = node.cnt;
            int curPipe = map[row][col];
 
            if (cnt < L)
                ans += 1;
            else
                continue;
 
            for (int i = 0; i < 4; i++) {
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc]) {
                    int nextPipe = map[nr][nc];
                    if (isPossible(curPipe, nextPipe, i)) {
                        visited[nr][nc] = true;
                        q.offer(new Node(nr, nc, cnt + 1));
                    }
                }
            }
        }
    }
 
    public static boolean isPossible(int curPipe, int nextPipe, int dir) {
 
        boolean flag = false;
 
        if (curPipe == 1) {
 
            if (dir == 0) {
                if (nextPipe == 1 || nextPipe == 3 || nextPipe == 6 || nextPipe == 7)
                    flag = true;
            } else if (dir == 1) {
                if (nextPipe == 1 || nextPipe == 3 || nextPipe == 4 || nextPipe == 5)
                    flag = true;
 
            } else if (dir == 2) {
                if (nextPipe == 1 || nextPipe == 2 || nextPipe == 4 || nextPipe == 7)
                    flag = true;
            } else {
                if (nextPipe == 1 || nextPipe == 2 || nextPipe == 5 || nextPipe == 6)
                    flag = true;
            }
 
        } else if (curPipe == 2) {
 
            if (dir == 2) {
                if (nextPipe == 1 || nextPipe == 2 || nextPipe == 4 || nextPipe == 7)
                    flag = true;
            } else if (dir == 3) {
                if (nextPipe == 1 || nextPipe == 2 || nextPipe == 5 || nextPipe == 6)
                    flag = true;
            }
 
        } else if (curPipe == 3) {
 
            if (dir == 0) {
                if (nextPipe == 1 || nextPipe == 3 || nextPipe == 6 || nextPipe == 7)
                    flag = true;
            } else if (dir == 1) {
                if (nextPipe == 1 || nextPipe == 3 || nextPipe == 4 || nextPipe == 5)
                    flag = true;
            }
 
        } else if (curPipe == 4) {
 
            if (dir == 0) {
                if (nextPipe == 1 || nextPipe == 3 || nextPipe == 6 || nextPipe == 7)
                    flag = true;
            } else if (dir == 3) {
                if (nextPipe == 1 || nextPipe == 2 || nextPipe == 5 || nextPipe == 6)
                    flag = true;
            }
 
        } else if (curPipe == 5) {
 
            if (dir == 0) {
                if (nextPipe == 1 || nextPipe == 3 || nextPipe == 6 || nextPipe == 7)
                    flag = true;
            } else if (dir == 2) {
                if (nextPipe == 1 || nextPipe == 2 || nextPipe == 4 || nextPipe == 7)
                    flag = true;
            }
 
        } else if (curPipe == 6) {
 
            if (dir == 1) {
                if (nextPipe == 1 || nextPipe == 3 || nextPipe == 4 || nextPipe == 5)
                    flag = true;
            } else if (dir == 2) {
                if (nextPipe == 1 || nextPipe == 2 || nextPipe == 4 || nextPipe == 7)
                    flag = true;
            }
 
        } else if (curPipe == 7) {
 
            if (dir == 1) {
                if (nextPipe == 1 || nextPipe == 3 || nextPipe == 4 || nextPipe == 5)
                    flag = true;
            } else if (dir == 3) {
                if (nextPipe == 1 || nextPipe == 2 || nextPipe == 5 || nextPipe == 6)
                    flag = true;
            }
        }
        return flag;
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
 
    public static void showMap(int[][] map) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
 
class Node {
    int row;
    int col;
    int cnt;
 
    public Node(int row, int col, int cnt) {
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
 
}