[SWEA] 1953.탈주범 검거(시뮬레이션,완탐).java

#. Problem

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

* The copyright in this matter is in SWEA

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

주어진 소요 시간 안에

이동할 수 있는 위치로 이동해보는 것인데,

터널 구조물 타입에 맞게 이동 가능 여부를 더 확인해주어야 한다.

풀이 방법은 정말 다양하다.

접근 방법에 따라 정말 복잡해질 수도..

정말 간단해질 수도 있는 것 같다.

구조물의 type 관리를 bitmask 를 활용해서도 해결할 수 있다고 하는데

bitmask 를 활용해서 다시 풀어봐야겠다.

#. Code_Naive

Naive 하게 bfs로 해결한 방법이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution1953 {
 
    static int H, W, R, C, L, res, map[][];
    static boolean[][] visited;
    static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
    static int[][] nextType = { { 1, 2, 5, 6 }, { 1, 2, 4, 7 }, { 1, 3, 4, 5 }, { 1, 3, 6, 7 } };
    static class State {
        int r, c, cnt;
 
        public State(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
 
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            st = new StringTokenizer(br.readLine());
            H = Integer.parseInt(st.nextToken()); // 지하 터널의 크기
            W = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken()); // 맨홀 뚜껑의 위치
            C = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken()); // 탈출 후 소요 시간
 
            map = new int[H][W];
            visited = new boolean[H][W];
            for (int r = 0; r < H; r++) {
                st = new StringTokenizer(br.readLine());
                for (int c = 0; c < W; c++) {
                    map[r][c] = Integer.parseInt(st.nextToken());
                }
            }
 
            res = 1;
            process();
            
            System.out.println("#" + tc + " " + res);
        }
    }
 
    private static void process() {
 
        State[] next = new State[4]; // 상,하,좌,우
        Queue<State> q = new LinkedList<>();
        // 초기 위치
        q.add(new State(R, C, 1));
        visited[R][C] = true;
 
        while (!q.isEmpty()) {
 
            State now = q.poll();
            // 소요 시간에 도달하면 종료
            if (now.cnt == L) return;
 
            int type = map[now.r][now.c];
            // 다음으로 좌표를 미리 저장
            for (int d = 0; d < 4; d++) {
                int rr = now.r + dr[d];
                int cc = now.c + dc[d];
                // 범위를 벗어나거나 이미 방문한 곳이거나 길이 없으면 -1
                if (rr < 0 || rr >= H || cc < 0 || cc >= W || visited[rr][cc] || map[rr][cc] == 0) {
                    next[d] = new State(-1, -1, -1);
                } else {
                    next[d] = new State(rr, cc, now.cnt + 1);
                }
            }
 
            State nLoc;
            // 연결된 터널을 찾고 다음 위치로 갈 수 있을 경우 queue에 추가
            // 위에 있는 터널과 연결될 경우
            if (type == 1 || type == 2 || type == 4 || type == 7) {
                nLoc = next[0];
                if (check(nLoc, 0)) q.add(nLoc);
            }
            // 아래에 있는 터널과 연결될 경우
            if (type == 1 || type == 2 || type == 5 || type == 6) {
                nLoc = next[1];
                if (check(nLoc, 1)) q.add(nLoc);
            }
            // 좌측에 있는 터널과 연결될 경우
            if (type == 1 || type == 3 || type == 6 || type == 7) {
                nLoc = next[2];
                if (check(nLoc, 2)) q.add(nLoc);
            }
            // 우측에 있는 터널과 연결될 경우
            if (type == 1 || type == 3 || type == 4 || type == 5) {
                nLoc = next[3]; 
                if (check(nLoc, 3)) q.add(nLoc);
            }
        }
    }
 
    private static boolean check(State next, int dir) {
 
        // 다음 위치로 갈 수 없다면
        if (next.r == -1)
            return false;
 
        int nType = map[next.r][next.c]; // 다음 위치의 구조물
        boolean isPos = false;
        for (int i = 0; i < 4; i++) {
            if (nextType[dir][i] == nType)
                isPos = true;
        }
        // 다음 위치에 갈 수 있는 구조물이 없다면
        if (!isPos)
            return false;
 
        visited[next.r][next.c] = true;
        res++;
 
        return true;
    }
 
}

line 72~81) 이동할 수 있는 사방 좌표를 먼저 저장해둔 후

line 86~104) 구조물 타입에 맞게 이동시켰다. 이동할 수 있다면 queue에 넣어주자.

line 108~128) check() 함수에서는 다음 좌표로 이동할 수 있는지 여부를 체크해준다.

#. Code_dfs (manage state by string)

bitmask 대신 String 으로 

구조물 타입이 연결된 방향을 관리해준 방법이다.

참고하면 좋을 것 같다.

bitmask 의 쉬운 버젼(?)이라고 생각한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution1953_dfs {
 
    static int N, M, R, C, L, map[][];
    static int visited[][];
    static int[] dr = {-1, 0, 0, 1}, dc = {0, -1, 1, 0};
    // 구조물 타입이 연결된 방향
    // 상,좌,우,하 : 0,1,2,3
    static String[] type = {
            null,
            "0312", // 1
            "03", // 2
            "12", // 3
            "02", // 4
            "32", // 5
            "31", // 6
            "01" // 7
    };
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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()); // 지하 터널의 크기
            M = Integer.parseInt(st.nextToken()); 
            R = Integer.parseInt(st.nextToken()); // 맨홀 뚜껑의 위치
            C = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken()); // 소요된 시간
            
            map = new int[N][M];
            visited = new int[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());
                    // 언제(time) 방문했는지 체크하기 위한 visited 배열을 MAX 값으로 초기화
                    visited[i][j] = Integer.MAX_VALUE;
                }
            }
            
            process(R, C, 1);
            System.out.println("#" + tc + " " + getCount());
        }
        
    }
    
    private static void process(int r, int c, int time) {
        
        // 방문 시간 저장
        visited[r][c] = time;
        // 소요 시간에 도달하면 종료
        if(time == L) return;
        
        // 구조물의 방향 정보
        String info = type[map[r][c]];
        int dir, rr, cc;
        for (int d = 0; d < info.length(); d++) {
            // 연결된 방향
            dir = info.charAt(d) - '0';
            // 연결된 다음 좌표
            rr = r + dr[dir];
            cc = c + dc[dir];
            // 범위를 벗어나거나 구조물이 없는 곳이라면 pass
            if(rr < 0 || rr >= N || cc < 0 || cc >= M || map[rr][cc] == 0) continue;
            // 다음 좌표의 구조물이 현재 방향과 연결되어있고 최근에 방문하지 않은 곳이면
            if(type[map[rr][cc]].contains(Integer.toString(3 - dir)) && visited[rr][cc] > time) {
                process(rr, cc, time + 1);
            }
        }
        
    }
    
    private static int getCount() { 
        
        int cnt = 0;
        // L 시간동안 지나온 모든 위치의 개수 count
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(visited[i][j] != Integer.MAX_VALUE) cnt++;
            }
        }
        
        return cnt;
    }
    
}

이동 방향을 상, 좌, 우, 하

           0 , 1,  2,  3

으로 설정한 이유에는 엄청난 비밀이 있다...

line 75. 에서

type[map[rr][cc]].contains(Integer.toString(3 - dir))

3 - dir 를 활용하기 위함이다.

예를 들어서,

상(0)으로 이동하기 위해서는 다음 좌표의 구조물의 하(3)가 연결되어있어야 하고

좌(1)로 이동하기 이해서는 다음 좌표의 구조물의 우(2)가 연결되어있어야 한다.

여기에 3 - dir 을 적용해보면

3 - 0(상) = 3(하)

3 - 1(좌) = 2(우)

가 된다.

최적화된 해결방법으로 if 문의 늪에서 살아날 수 있다는 것을 알게 되었다..

문제를 많이 풀다 보면 나도 언젠가는.. 이렇게 신박한 방법을 바로 떠올릴 수 있겠지/..!

#. Code_bfs (manage state by string)

 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution1953_BFS_teacher {
 
    static int N, M, R, C, L, map[][];
    static boolean visited[][];
    static int[] dr = {-1, 0, 0, 1}, dc = {0, -1, 1, 0};
    // 구조물 타입이 연결된 방향
    // 상,좌,우,하 : 0,1,2,3
    static String[] type = { 
            null, 
            "0312", // 1: 상하좌우
            "03", // 2:상하
            "12", // 3:좌우
            "02", // 4:상우
            "32", // 5:하우
            "31", // 6:하좌
            "01" // 7:상좌
    };
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(in.readLine());
        for (int tc = 1; tc <= T; ++tc) {
            st = new StringTokenizer(in.readLine().trim());
            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()); // 소요된 시간
            
            map = new int[N][M];
            visited = new boolean[N][M];
 
            for (int i = 0; i < N; ++i) {
                st = new StringTokenizer(in.readLine().trim());
                
                for (int j = 0; j < M; ++j) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            System.out.println("#" + tc + " " + process());
        }
    }
 
    private static int process() {
        
        // 시작 위치도 시간에 포함 : cnt = res = 1
        int res = 1, time = 1, size = 0;
        
        Queue<Point> queue = new LinkedList<>();
        // 시작 위치
        queue.add(new Point(R, C));
        visited[R][C] = true;
        
        String info = null;
        while (time++ < L) {
            // 1시간 동안 이루어지는 동작
            size = queue.size();
            
            while (size-- > 0) {
                // 현재 위치
                Point now = queue.poll();
                // 현재 위치에서 이동할 수 있는 방향 정보
                info = type[map[now.x][now.y]];
 
                for (int d = 0; d < info.length(); d++) {
                    // 연결된 방향
                    int dir = info.charAt(d) - '0';
                    // 연결된 다음 좌표
                    int rr = now.x + dr[dir];
                    int cc = now.y + dc[dir];
                    // 범위를 벗어나거나 구조물이 없는 곳이라면 pass
                    if(rr < 0 || rr >= N || cc < 0 || cc >= M || map[rr][cc] == 0) continue;
                    // 다음 좌표의 구조물이 현재 방향과 연결되어있고 방문하지 않은 곳이면
                    if(type[map[rr][cc]].contains(Integer.toString(3 - dir)) && !visited[rr][cc]) {
                        queue.add(new Point(rr, cc));
                        visited[rr][cc] = true;
                        res++;
                    }
                }
            }
        }
        
        return res;
    }
}