[SWEA] 1953. 탈주범 검거

풀이

• 파이프의 유형에 따라 갈 수 있는 방향이 달라지고 next 위치가 그 "정반대" 방향을 보유한 파이프여야 next로 갈 수 있다. 예를 들어, 현재 위치에서 "상"방향을 나아가고자 한다면 next위치에는 "하"방향을 가진 파이프여야 next로 진행이 가능하다.

1. 탐색지점 -> 범위 내
2. 미방문했는지
3. 연결 가능한지 판단

• 파이프 정형화 => 3의 보수를 사용해서 보다 간결한 코드 작성을 할 수 있다.
  타입 별로 갈 수있는 방향
• BFS와 DFS 모두 가능하지만 자연스럽게 최단거리가 보장되는 BFS와 달리 DFS는 최단거리일 경우, 이미 방문된 위치라도 조건에 따라 새로 방문할 수 있도록 하는 코드 작성이 필요해서 더 복잡하다.
  👉🏻 vis값 비교를 통해서 더 이른 시간에 도착이 가능하다면 진행한다. 그래도 이미 값이 존재한다면 ANS 카운트는 증가x

BFS 코드

package SWEA_AD;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_1953_탈주범검거{

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;

	static int T;
	static int N,M,R,C,L;
	private static int[][] map;
	private static int A;
	private static int dir[][] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; // 3의 보수를 사용하기 위해 -> 상 좌 우 하
	private static int type[][] = {
			{},
			{0, 1, 2, 3},
			{0, 3},
			{1, 2},
			{0, 2},
			{2, 3},
			{1, 3},
			{0, 1}
	};

	public static void main(String[] args) throws NumberFormatException, IOException {
		T = Integer.parseInt(input.readLine());
		for(int t=1;t<=T; t++) {
			tokens = new StringTokenizer(input.readLine());
			N = Integer.parseInt(tokens.nextToken());
			M = Integer.parseInt(tokens.nextToken());
			R = Integer.parseInt(tokens.nextToken());
			C = Integer.parseInt(tokens.nextToken());
			L = Integer.parseInt(tokens.nextToken()); //탈출 소요된 시간

			map = new int[N][M];
			for(int i = 0; i < N; i++) {
				tokens = new StringTokenizer(input.readLine());
				for(int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(tokens.nextToken());
				}
			} //end of 입력
			A = 0;
			bfs();
			output.append(String.format("#%d %d%n", t, A));
		}
		System.out.println(output);
	}

	static void bfs() {
		Queue<Pipe> q = new LinkedList<>();
		boolean[][] vis = new boolean[N][M];
		q.offer(new Pipe(R, C, map[R][C])); //멘홀 뚜껑 위치(시작위치)
		L--;//멘홀 뚜껑에 가기 위한 1시간
		A++;
		vis[R][C] = true;

		while(!q.isEmpty()) {
			if(L == 0) break;
			int size = q.size();
			while(size -- > 0) {
				Pipe p = q.poll();
				//파이프 유형에 따라서 갈 수 있는 방향이 달라진다.
				int[] typeDir = type[p.type];
				for(int d : typeDir) {
					int nr = p.r + dir[d][0];
					int nc = p.c + dir[d][1];
					//가고자하는 위치의 파이프가 현재 p의 반대 방향으로 받아줄 수 있어야함
					if(isIn(nr, nc) && !vis[nr][nc] &&possibleDir(nr, nc, 3-d)) {
						vis[nr][nc] =true;
						q.offer(new Pipe(nr, nc, map[nr][nc]));
						A++;
					}
				}
			}
			L--;
		}
	}

	private static boolean possibleDir(int nr, int nc, int d) {
		int[] tmpTypeDir = type[map[nr][nc]];
		for(int x : tmpTypeDir) {
			if(x == d) return true;
		}
		return false;
	}

	static class Pipe{
		int r,c,type;
		public Pipe(int r, int c, int type) {
			this.r = r;
			this.c = c;
			this.type = type;
		}
	}
	static boolean isIn(int r, int c) {
		return 0 <= r && r < N && 0 <= c && c < M;
	}

DFS 코드

package SWEA_AD;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// bfs: 39,780 kb, 138 ms,  dfs: 37,768 kb, 130 ms

public class SWEA_모의_1953_탈주범검거 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;

    // 대상을 단순화 - 3의 보수
    static int[][] deltas = { { -1, 0 }, { 0, -1 }, 
    		{ 0, 1 }, { 1, 0 } }; // 상.좌 | 우, 하
    // 파이프 규정해두기
    static int[][] types = {
            {},
            { 0, 1, 2, 3 }, // 상하좌우
            { 0, 3 }, // 상하
            { 1, 2 }, // 좌우
            { 0, 2 }, // 상,우
            { 2, 3 }, // 우,하
            { 1, 3 }, // 좌,하
            { 0, 1 }// 상, 좌
    };

    static int T;
    static int N, M, R, C, L;
    static int[][] map;
    static int A;

    public static void main(String[] args) throws NumberFormatException, IOException {
        T = Integer.parseInt(input.readLine());
        for (int t = 1; t <= T; t++) {
            tokens = new StringTokenizer(input.readLine());
            N = Integer.parseInt(tokens.nextToken());
            M = Integer.parseInt(tokens.nextToken());
            R = Integer.parseInt(tokens.nextToken());
            C = Integer.parseInt(tokens.nextToken());
            L = Integer.parseInt(tokens.nextToken());

            map = new int[N][M];
            for (int n = 0; n < N; n++) {
                tokens = new StringTokenizer(input.readLine());
                for (int m = 0; m < M; m++) {
                    map[n][m] = Integer.parseInt(tokens.nextToken());
                }
            }
            /*
            for (int[] row : map) {
                System.out.println(Arrays.toString(row));
            }
            */
            // 입력 완료

            // 입력받지 않는 전역 변수는 초기화!!!
            A = 0;
             bfs();
            //dfs(R, C, L, new int[N][M]);
             output.append(String.format("#%d %d%n", t, A));
        }
        System.out.println(output);
    }

    static void dfs(int r, int c, int l, int[][] visited) {
        // base part
        if (l == 0) {
            return;
        }
        // 할일 처리 : 순서 주의!!! 먼저 체크 하고 방문 처리!!
        // 방문지 증가 : 처음 방문 했을 때만.
        if (visited[r][c] == 0) {
            A++;
        }
        // 방문 처리
        visited[r][c] = l; //1이 아닌 l

        // 자식 탐색
        int[] open = types[map[r][c]];
        for (int d : open) {
            int nr = r + deltas[d][0];
            int nc = c + deltas[d][1];
            
            //vis값이 현재 l보다 작다면 => 즉 더 이른 시간에 도착이 가능하다면 진행한다.
            //그래도 이미 값이 존재한다면 A는 증가x
            if (isIn(nr, nc) && visited[nr][nc] < l && map[nr][nc] != 0 
            		&& canConnect(nr, nc, 3 - d)) { //3의 보수: d == 0 -> 위로 갈 때, 받아줄 수 있는 파이프인지 확인
            	// 3-d => 3 : next 위치의 파이프가 "하 방향"일 때 받아줄 수 있다.
                dfs(nr, nc, l - 1, visited);
            }
        }
    }

    static void bfs() {
        // 준비물
        Queue<Pipe> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];

        // 초기화
        q.offer(new Pipe(R, C));
        visited[R][C] = true;
        L--; // 현재 한시간 경과!
        A = 1;// 맨홀의 위치 확보!!

        while (L > 0) {
            // 현재 queue에 있는 녀석들만 먼저 돌리기!!
            int size = q.size();

            while (size-- > 0) {
                // 대장 데려오기
                Pipe head = q.poll();

                for (int d : head.open) {
                    int nr = head.r + deltas[d][0];
                    int nc = head.c + deltas[d][1];

                    // 대상지점의 파이프와 연결할 수 있어야 한다.
                    // 영역 안에 있고, 미방문이고, 파이프이면서 연결할수 있다면????
                    if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] != 0 && canConnect(nr, nc, 3 - d)) {
                        visited[nr][nc] = true;
                        q.offer(new Pipe(nr, nc));
                        A++;
                    }
                }
            }
            L--; // 한시간 경과
        }
    }

    /**
     * r, c의 pipe는 d 방향이 열려있는가?
     * 
     * @param r
     * @param c
     * @param d
     * @return
     *
     *
     */
    static boolean canConnect(int r, int c, int d) { //
        for (int i : types[map[r][c]]) {
            if (i == d) {
                return true;
            }
        }
        return false;
    }

    static boolean isIn(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < M;
    }

    static class Pipe {
        int r, c;
        int[] open;

        public Pipe(int r, int c) {
            this.r = r;
            this.c = c;
            this.open = types[map[r][c]];
        }
    }