[ Baekjoon - 10/25 ] - 1600번: 말이 되고픈 원숭이

• 문제 링크 : https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

• 소요 시간 : 2시간

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 256MB
   • 문제
     
     • 원숭이가 점프 할 수 있는 횟수K(0≤K≤30), 지도의 가로W, 세로 H(1≤W,H≤200)
     • 원숭이가 한번에 상하좌우 한칸씩 갈 수 있는데, K번만큼 체스의 나이트처럼 움직일 수 있을 때
       최소 몇번의 이동으로 도착지(지도의 가장 우측하단)까지 갈 수 있는지 출력하는 문제
   • 이해
     • 지도에서의 이동이므로 완탐이라 생각했다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 원숭이가 움직일 수 있는 좌표를 그려보고, 점프하는 이동이 무조건적으로 좋은 이동인지 분석해보았다.
   • 점프하는 곳이 우측하단이면 무조건적으로 좋다고 생각될수도 있지만, 장애물이 다양하게 배치될 수 있으므로 이를 단정짓기란 어려워보였음.
   • 결국 완탐이라 생각했다.
3. 문제를 어떻게 해결할 것인가
   
   • 완탐에는 크게 두가지가 있다. DFS와 BFS.
   • 기본형태의 경우 DFS는 N! 의 시간복잡도, BFS는 맵크기의 시간복잡도를 가진다.
   • 1st 접근 - BFS, 이동횟수는 vis를 dp처럼 이용하기)

     • 

     • 위의 흐름처럼 짜면된다고 생각했고 당시엔 오류가 없을거라 생각해 그대로 코딩했다. 
     • 당연히 돌아갈 줄 알았던 코드에서는 큰 오류가 하나 있었는데, 바로 BFS이기때문에 체크인이 어떻게 이동한 애를 위한 체크인인지 모른다는 것이었다.
     • 그래서 어떻게 체크인을 때에따라 다르게 체킹할수있을지 고민했지만 결국 생각나지 않아서 vis를 어떻게 잠잡았는지 다른 분들 코드를 찾아봤다.
     • 다들 정수형 3중 리스트로 구현해 놓은것을 보고 너무 시간복잡도가 크지않나 싶으면서도 결국 삼중리스트로 구현해보기로 했다.
     • 자바에서는 겨우겨우 성공했지만 역시나 파이썬으로 치환하니 성공은했지만 소요시간이 굉장히 컸다..
     • 그래서 다른 방법을 생각해보기로 했다.
   • 2nd 접근 - BFS, 이동횟수는 BFS의 특징을 이용해 단순화, vis는 boolean형으로 구현)
     • 최적화하기위해서는 우선 정수형 3중리스트...를 부숴야했다. 얘를 들고가서는 줄이는게 매우 힘들어보이므로.. 
     • 3중리스트를 가져온 이유가 어느 아이의 방문여부인지 알기 위함이었으니 vis를 보통 많이 쓰는 boolean형으로 바꿔보고자 했다.
     • 첫번째 접근에서 vis는 이동한 횟수를 들고있었다. 이를 어떻게 빼낼 수 있을지 생각하던 때, BFS는 큐에서 가져온 노드를 기준으로 한번의 이동만으로 어디를 갈 수 있는지 분석하고 다시 큐에 넣는 작업을 하기때문에 결국! 한번의 while문 루프마다 이동횟수+1하는 형태이므로 반복문을 다시 수행할때 값을 더해서 들고있게 하면 된다고 생각했다!
     • 이렇게 최적화를 하니 거의 반이상의 시간이 절감되었다~
4. 위 계획을 검증
   • k까지 고려한 vis이므로, 오류는 없다고 생각한다. 좀더 풀어쓰고싶지만 내 어휘력은...
5. 계획 수행 (실제코드 작성)
   1. Java 11 - 첫번째 접근 풀이

      • import java.util.*;
        import java.io.*;
        
        public class Main{
            static int K,W,H,ans=-1;
            static int[][] map;
            static int[][][] vis;
            // 상, 하 좌 우, 시계방향
            static int[] dx = {-1,1,0,0,-2,-1,1,2,2,1,-1,-2}, dy={0,0,-1,1,1,2,2,1,-1,-2,-2,-1};
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
        
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                K = Integer.parseInt(br.readLine());
        
                StringTokenizer st = new StringTokenizer(br.readLine());
                W = Integer.parseInt(st.nextToken());
                H = Integer.parseInt(st.nextToken());
        
                map = new int[H][W];
                for (int h = 0; h < H; h++) {
                    st = new StringTokenizer(br.readLine());
                    for (int w = 0; w < W; w++) {
                        map[h][w] = Integer.parseInt(st.nextToken());
                    }
                }
                vis = new int[H][W][K+1];
                BFS();
                System.out.println(ans);
            }
        
            private static void BFS() {
                Queue<Point> queue = new LinkedList<>();
                queue.add(new Point(K,0,0,0));
        
                while(!queue.isEmpty()) {
                    //1. 큐에서 꺼내옴
                    Point node = queue.poll();
                    //2. 목적지인가
                    if(node.x == H-1 && node.y == W-1){
                        ans = vis[node.x][node.y][node.k];
                        return;
                    }
                    //3. 연결되어있는가
                    for (int i = 0; i < 12; i++) {
                        int nx = node.x + dx[i];
                        int ny = node.y + dy[i];
                        //4. 갈 수 있는가 - 맵안, 평지, 방문X
                        if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny]==0){
                            // 상하좌우 라면
                            if(i<4){
                                if(vis[nx][ny][node.k]==0) {
                                    //5. 체크인
                                    vis[nx][ny][node.k] = vis[node.x][node.y][node.k]+1;
                                    //6. 큐에넣음
                                    queue.add(new Point(node.k, nx, ny, node.curCnt + 1));
                                }
                            }else if(node.k>0 && vis[nx][ny][node.k-1]==0){
                                //5. 체크인
                                vis[nx][ny][node.k-1] = vis[node.x][node.y][node.k]+1;
                                //6. 큐에넣음
                                queue.add(new Point(node.k-1,nx,ny, node.curCnt+1));
                            }
                        }
                    }
                }
            }
        }
        
        class Point{
            int k;
            int x,y;
            int curCnt;
        
            public Point(int k, int x, int y, int curCnt) {
                this.k = k;
                this.x = x;
                this.y = y;
                this.curCnt = curCnt;
            }
        
            @Override
            public String toString() {
                return "Point{" +
                        "k=" + k +
                        ", x=" + x +
                        ", y=" + y +
                        ", curCnt=" + curCnt +
                        '}';
            }
        }

   2. Python 3 - 최적화를 수행한 풀이

      • import sys
        from collections import deque
        
        # sys.stdin = open("input.txt")
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
        
        def BFS(K, H, W, board):
            if H == 1 and W == 1:
                return 0
        
            vis = [[[False] * W for _ in range(H)] for _ in range(K + 1)]
            queue = deque([(0, 0, K)])
            dist = 0
            while queue:
                # 이 루프에선 같은 +1만으로 갈 수 있는 경우를 큐에 +하므로 이동횟수를 +1로 단순화 할 수 있음.
                dist += 1
                for _ in range(len(queue)):
                    # 1. 큐에서 꺼내옴
                    x, y, k = queue.popleft()
        
                    # 3. 연결되어있는가 - 상하좌우
                    for (dx, dy) in dirs[:4]:
                        nx, ny = x + dx, y + dy
                        # 4. 갈 수 있는가 - 맵안, 평지, 방문X 경우 제외 불가
                        if nx < 0 or nx >= H or ny < 0 or ny >= W or vis[k][nx][ny] or board[nx][ny] == '1':
                            continue
                        # 2. 목적지인가 - 마지막 위치인가
                        if nx == H-1 and ny == W-1:
                            return dist
                        # 5. 체크인
                        vis[k][nx][ny] = True
                        # 6. 큐에넣음
                        queue.append((nx, ny, k))
        
                    # X 위치로 점프 할 수 있을때는 k에 0이 아닌 양수가 있을때 이므로
                    if k > 0:
                        # 3. 연결되어있는가 - X 위치들
                        for (dx, dy) in dirs[4:]:
                            nx, ny = x + dx, y + dy
                            # 4. 갈 수 있는가 - 맵안, 평지, 방문X 경우 제외 불가
                            if nx < 0 or nx >= H or ny < 0 or ny >= W or vis[k - 1][nx][ny] or board[nx][ny] == '1':
                                continue
                            # 2. 목적지인가 - 마지막 위치인가
                            if nx == H-1 and ny == W-1:
                                return dist
                            # 5. 체크인 - k값 감소해야함
                            vis[k - 1][nx][ny] = True
                            # 6. 큐에넣음
                            queue.append((nx, ny, k - 1))
            return -1
        
        if __name__ == '__main__':
            K = int(sys.stdin.readline())
            W, H = map(int, sys.stdin.readline().split())
            board = [list(sys.stdin.readline().split()) for _ in range(H)]
            print(BFS(K, H, W, board))

 

• 결과