[Java] 백준 2314. 이세계 게임

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

 

 

---

 

 

 

 

 

 

문제

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

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

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

 

 

 

입력

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

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

 

 

 

출력

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

 

 

 

 

 

 

---

 

 

풀이

16개의 위치를 비트마스크를 통해 하나의 정수로 변환하여 풀 수 있다.

P는 1로, L은 0으로 설정한다. 

 

예를 들어 아래와 같은 초기 배치가 주어졌다고 하자.

LLLL
PPPP
LLLP
PPLP

이 배치를 비트마스크로 변환한다면 0000111110001010 형태가 된다. 

 

이처럼 초기 상태와 목표 상태를 비트마스킹을 통해 정수로 변환해 준 후

bfs로 원하는 배치를 만들기 위해 필요한 최소 자리바꿈 횟수를 구해주면 된다. 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

// https://www.acmicpc.net/problem/2314
public class Main {
    private static final int[] DR = {-1, 1, 0, 0};
    private static final int[] DC = {0, 0, -1, 1};
    private static final int N = 4;
    private static final int TOTAL = 16;
    private static int origin;
    private static int target;


    public static void main(String[] args) throws IOException {
        init();

        int count = getCount();
        System.out.print(count);
    }//main


    private static int getCount() {
        Queue<int[]> q = new LinkedList<>();
        boolean[] visited = new boolean[1 << TOTAL];

        q.offer(new int[] {origin, 0});
        visited[origin] = true;

        int[] cur;
        int status, move;
        int r, c, nr, nc;

        while(!q.isEmpty()) {
            cur = q.poll();
            status = cur[0]; // 현재 상태
            move = cur[1]; // 이동 횟수

            // 택희가 원하는 배치 완성
            if(status == target) return move;

            for(int i=0, m=1; i<TOTAL; i++, m<<=1) {
                if((status & m) == 0) continue;

                r = i / N;
                c = i % N;

                for(int d=0; d<4; d++) {
                    nr = r + DR[d];
                    nc = c + DC[d];

                    if(rangeCheck(nr, nc)) continue;

                    // 다음 칸으로 이동가능한지 확인
                    int nm = 1 << (nr * N + nc);
                    if((status & nm) != 0) continue;

                    // 다음 칸으로 이동
                    int next = (status ^ m) | nm;
                    if(visited[next]) continue;

                    visited[next] = true;
                    q.offer(new int[] {next, move + 1});
                }
            }
        }

        return -1;
    }//getCount


    private static boolean rangeCheck(int r, int c) {
        return r < 0 || r >= N || c < 0 || c >= N;
    }//rangeCheck


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] row;

        // 현재 주민들의 배치
        for(int i=0; i<N; i++) {
            row = br.readLine().toCharArray();
            for(int j=0; j<N; j++) {
                if(row[j] == 'P') origin |= 1 << (i * N + j);
            }
        }

        br.readLine();

        // 택희가 원하는 배치
        for(int i=0; i<N; i++) {
            row = br.readLine().toCharArray();
            for(int j=0; j<N; j++) {
                if(row[j] == 'P') target |= 1 << (i * N + j);
            }
        }

        br.close();
    }//init


}//class