[ Baekjoon - 10/28 ] - 2314번: 이세계 게임

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

2314번: 이세계 게임

 

• 소요 시간 : 30분

 

이세계 게임

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

64

27

23

41.071%

문제

트럭 운전사 택희는 오랜 기간 동안의 공로를 인정받아 이세계로 소환되었다. 택희가 소환된 이세계에는 천사 종족 Portableangel과 악마 종족 Legnaelbatrop이 살고 있었다. 택희는 뛰어난 알고리즘 지식을 발휘해 얼마 지나지 않아 두 종족을 모두 지배하는 이세계의 왕이 되었다.

폭군 택희는 지루해지면 이세계의 주민들을 이용해 게임을 한다. 먼저 종족과 무관하게 16명의 개체를 모아서 4×4 격자 형태로 세워 놓는다. 그 다음 각 자리에 어떤 종족이 서야 하는지를 지정해 주고, 그에 맞게 다시 서도록 명령한다. 그러면 이들은 서로 자리를 바꿔서 택희가 원하는 배치를 만들어야 한다. 자리를 바꿀 때는 상하좌우로 인접한 두 개체끼리만 바꿀 수 있으며, 한 개체가 여러 번 자리를 바꿀 수도 있다.

현재 주민들의 배치와 택희가 원하는 배치가 주어질 때, 최소 몇 번의 자리 바꿈이 필요한지 구하여라.

입력

'P' 또는 'L'을 값으로 갖는 4×4 행렬이 공백 없이 주어진다. 이는 현재 주민들의 배치를 나타내며, 'P'는 Portableangel, 'L'은 Legnaelbatrop 종족을 뜻한다.

그 다음 빈 줄이 0개 이상 주어진 뒤 택희가 원하는 배치가 같은 방식으로 주어진다. 택희에게는 최소한의 양심이 있기에 불가능한 배치는 주어지지 않는다.

출력

택희가 원하는 배치를 만들기 위해 필요한 최소 자리 바꿈 횟수를 출력한다.

예제 입력 1 복사

LLLL
PPPP
LLLP
PPLP

LPLP
PLPL
LPLP
PLPL

예제 출력 1 복사

4

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     
     • 4 x 4의 지도, P와 L 두종류의 글자로 구성
     • 현재맵과 원하는맵이 주어질때 최소의 이동횟수를 출력하는 문제
       여기서 이동은, 대각선 방향이 아닌 인접한 한칸만이 가능하다.
   • 이해
     • 문제 이해에 어려움은 없었지만, 어떻게 풀어야할지 많은 고민을 했었다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 이해가 어렵진 않아서 크게 그려보진 않았다. 3번에서 규칙을 얻기위해 그려봤음.
3. 문제를 어떻게 해결할 것인가

   • 

   • 1st 접근 - 가장자리부터 접근하기)
   • 중간에 있는 아이들은 상하좌우 영역으로 바꿀 수있지만, 꼭짓점에 있는 아이들은 두방향밖에 되지 않아서,
     꼭짓점(4개) -> 선쪽(8개) -> 안쪽(4개)로 접근해야한다고 생각했다.
   • 위 생각은 너무 단순하게 상하좌우에 본인과 다른 (해당 좌표값이 L이면 P찾고, P면 L찾아야 하므로) 좌표가 존재할것이라 생각해서 얻은 해결책이었기 떄문에, 결국 여러번 탐색하면서 찾아가야하므로 굳이 가장자리부터 접근하지 않아도 될것이라 생각했다.
   • 2nd 접근 - 바꿔야하는 좌표를 L과 P에 따라 저장한뒤, L을 기준으로 가장 가까운 P를 찾아 바꾸기)
   • 총 거리값이 최소가 되기 위해서는, 바꿔야하는 곳의 길이또한 짧아야한다고 생각해서, L을 기준으로 가장 최소의 길이를 갖는 좌표로 바꿔줘야한다고 생각했다.
4. 위 계획을 검증
   • 해당 L좌표를 기준으로 가장 짧은곳에 있는 P를 찾는 식으로 진행하면, 가능하다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            private static class Node {
                boolean[][] map = new boolean[4][4];
                long hash = 0;
                int step = 0;
        
                Node(boolean[][] map, int step) {
                    for (int i = 0; i < 4; i++) {
                        for (int j = 0; j < 4; j++) {
                            this.map[i][j] = map[i][j];
                            if (map[i][j]) {
                                hash += (1 << (i * 4 + j));
                            }
                        }
                    }
                    this.step = step;
                }
        
                void swap(int x, int y, int nx, int ny) {
                    boolean temp = map[x][y];
                    map[x][y] = map[nx][ny];
                    map[nx][ny] = temp;
                }
        
                long getHash() {
                    return hash;
                }
            }
        
            static Node R;
            static int[] dx = { -1, 1, 0, 0 };
            static int[] dy = { 0, 0, -1, 1 };
            static Queue<Node> q = new LinkedList<>();
            static HashSet<Long> visit = new HashSet<>();
            static boolean map[][] = new boolean[4][4];
            static boolean result[][] = new boolean[4][4];
        
            public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                for (int i = 0; i < 4; i++) {
                    char[] temp = br.readLine().toCharArray();
                    for (int j = 0; j < 4; j++) {
                        map[i][j] = temp[j] == 'L';
                    }
                }
        
                for (int i = 0; i < 4; i++) {
                    char[] temp = br.readLine().toCharArray();
                    while (temp.length == 0) {
                        temp = br.readLine().toCharArray();
                    }
                    for (int j = 0; j < 4; j++) {
                        result[i][j] = temp[j] == 'L';
                    }
                }
        
                R = new Node(result, 0);
                q.add(new Node(map, 0));
                visit.add(q.peek().getHash());
        
                System.out.println(bfs());
            }
        
            private static int bfs() {
                boolean[][] temp = new boolean[4][4];
                while (!q.isEmpty()) {
                    Node now = q.poll();
                    if (now.getHash() == R.getHash()) {
                        return now.step;
                    }
                    for (int i = 0; i < 4; i++) {
                        for (int j = 0; j < 4; j++) {
                            temp[i][j] = now.map[i][j] != result[i][j];
                        }
                    }
        
                    for (int x = 0; x < 4; x++) {
                        for (int y = 0; y < 4; y++) {
                            for (int d = 0; d < 4; d++) {
                                int nx = x + dx[d];
                                int ny = y + dy[d];
        
                                if (nx >= 0 && ny >= 0 && nx < 4 && ny < 4) {
                                    now.swap(x, y, nx, ny);
                                    Node next = new Node(now.map, now.step + 1);
                                    if (!visit.contains(next.getHash())) {
                                        visit.add(next.getHash());
                                        q.add(next);
                                    }
                                    now.swap(x, y, nx, ny);
                                }
                            }
                        }
                    }
                }
                return -1;
            }
        }

   2. Python 3

      • import sys
        from collections import deque
        # sys.stdin = open("input.txt")
        
        dxy = ((-1,0),(1,0),(0,-1),(0,1))
        
        origiMap = [sys.stdin.readline().rstrip("\n") for _ in range(4)]
        temp = sys.stdin.readline()
        wantMap = [sys.stdin.readline().rstrip("\n") for _ in range(4)]
        
        changeL = []
        changeP = []
        
        ans=0
        for i in range(4):
            for j in range(4):
                if origiMap[i][j] != wantMap[i][j]:
                    changeL.append((i, j)) if origiMap[i][j] == 'L' else changeP.append((i, j))
        
        
        for i in range(len(changeL)):
            minDist = [9, 0]     # 거리가 9이고 좌표 0로 설정
            for j in range(len(changeP)):
                dist = abs(changeL[i][0]-changeP[j][0]) + abs(changeL[i][1]-changeP[j][1])
                if minDist[0] > dist:
                    minDist = [dist, j]
            ans += minDist[0]
            changeP.remove(changeP[minDist[1]])
        
        print(ans)

 

• 결과