Baekjoon 4577 소코반 JAVA

4577번: 소코반

문제

소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수는 같다. 플레이어는 화살표(위, 아래, 왼쪽, 오른쪽)를 이용해 캐릭터를 아래와 같은 규칙으로 조정할 수 있다.

• 캐릭터에게 지시한 방향이 빈칸(박스나 벽이 아닌 곳)인 경우에는 그 칸으로 이동한다.
• 지시한 방향에 박스가 있는 경우에는, 박스를 민다. 이 경우에는 박스가 이동할 칸도 비어있어야 한다.
• 지시한 방향이 벽인 경우, 또는 박스가 있는데, 박스가 이동할 칸에 다른 박스나 벽이 있는 경우에는 키를 눌러도 캐릭터는 이동하지 않는다.

모든 박스를 목표점으로 이동시킨 경우에 게임은 끝난다. 게임이 끝난 후에 입력하는 키는 모두 무시된다.

준규는 소코반으로 고통받는 친구들을 위해서 소코반의 해를 찾는 프로그램을 작성하려고 한다. 하지만, 소코반의 해를 찾는 문제는 NP-hard와 PSPACE-complete에 속하고, 매우 어려운 문제이다. 따라서, 간단한 소코반 프로그램을 작성해보려고 한다.

사용자가 입력한 키가 순서대로 주어졌을 때, 게임이 어떻게 진행되는지를 구하는 프로그램을 작성하시오.

게임의 상태는 아래와 같은 문자로 나타낼 수 있다.

문자 뜻

.	빈 공간
#	벽
+	비어 있는 목표점
b	박스
B	목표점 위에 있는 박스
w	캐릭터
W	목표점 위에 있는 캐릭터

첫 번째 입력은 문제의 그림과 같다.

조건

[입력]

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 행과 열의 수 R, C가 주어진다. (4 ≤ R ≤ 15, 4 ≤ C ≤ 15) 다음 R개 줄에는 현재 게임의 상태가 주어진다. 모든 줄은 C개의 문자로 이루어져 있다. 마지막 줄에는 플레이어가 입력한 키가 순서대로 주어지며 길이는 최대 50이다. 위, 아래, 왼쪽, 오른쪽은 U, D, L, R로 나타낸다.

입력의 마지막 줄에는 0 0이 주어진다.

입력으로 주어지는 모든 데이터는 항상 캐릭터가 한 명이고, 박스의 수와 목표점의 수는 같다. 또, 목표점 위에 올라가 있지 않은 박스는 적어도 한 개이며, 가장 바깥쪽 칸은 항상 벽이다.

 

[출력]

각각의 게임에 대해서, 게임 번호를 출력한 다음에 게임이 끝났으면 complete를, 아니면 incomplete를 출력한다. 그다음 줄부터 R개 줄에는 게임의 상태를 출력한다.

풀이

해당 문제는 어렸을 때 휴대폰으로 많이 했던 게임을 구현하는 문제다. 문제 자체는 어렵지 않았고 그저 시키는 대로 구현하면 되는 구현 문제다.

 

다만 처음 문제를 제대로 읽지 않아 게임에 성공하면 다음 명령어들을 무시한다는 문구들 체크하지 못했었다.

 

또한 최초 제출 시 50%에서 틀렸고 확인을 해보니 박스나 캐릭터가 처음부터 목표점에 있는 경우도 체크를 해줘야 하는데 해당 부분을 빼먹었기 때문이었다.

 

로직은 아래와 같은 방식으로 구현하였다.

 

1. 입력 처리를 한다 이때 캐릭터와 박스의 좌표를 저장한다.

2. 명령어를 모두 입력받고 하나씩 수행한다.

3. 명령어를 확인해 방향을 지정해주고 이동한다.

    3-1. 캐릭터가 이동하려는 곳이 빈칸이면 좌표를 갱신한다.

    3-2. 캐릭터가 이동하려는 곳이 박스면 그 다음칸을 체크한다.

        3-2-1. 그 다음칸이 빈칸이라면 박스를 이동시키고 캐릭터 좌표를 갱신한다.

4. 목표점에 모든 박스가 들어왔는지 체크한다.

5. 위와 같은 로직을 반복하고 최종적으로 출력한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int R, C, sy,sx, t , dy[] = {-1,1,0,0}, dx[]= {0,0,-1,1};
	static char map[][], cmd[];
	static List<Node> list;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			if(R ==0 && C == 0)
				break;
			map = new char[R][C];
			list = new LinkedList<>();
			for (int i = 0; i < R; i++) {
				map[i] = br.readLine().toCharArray();
				for (int j = 0; j < C; j++) {
					if(map[i][j] == 'w' ) { // 캐릭터 좌표 저장
						sy = i;
						sx = j;
						map[i][j] = '.';
					}else if(map[i][j] == 'W') { // 캐릭터 좌표 저장 + 목표물 좌표 저장
						list.add(new Node(i,j));
						sy = i;
						sx = j;
						map[i][j] = '.';
					}
					else if(map[i][j] == '+') { // 목표물 좌표 저장
						list.add(new Node(i,j));
						map[i][j] = '.';
					}else if(map[i][j] == 'B') { // 박스 데이터 변경 + 목표물 좌표 저장
						list.add(new Node(i,j));
						map[i][j] = 'b';
					}
				}
			}
			cmd = br.readLine().toCharArray(); // 이동해야하는 명령어 저장
			for (int i = 0; i < cmd.length; i++) {
				int n = 0; // 상
				if(cmd[i] =='D') // 하
					n = 1;
				else if(cmd[i] =='L') // 좌
					n = 2;
				else if(cmd[i] =='R') // 우
					n = 3;
				move(n);
				if(check())
					break;
			}
			print();
		}
	}
	
	private static void print() {
		int cnt = 0;
		map[sy][sx] ='w'; 
		for (int i = 0; i < list.size(); i++) {
			Node n = list.get(i);
			if(map[n.y][n.x] == 'b') {
				cnt++;
				map[n.y][n.x] = 'B';
			}else if(map[n.y][n.x] == 'w')
				map[n.y][n.x] = 'W';
			else
				map[n.y][n.x] = '+';
		}
		if(cnt == list.size())
			System.out.println("Game "+(++t)+": complete");
		else
			System.out.println("Game "+(++t)+": incomplete");
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}

	private static boolean check() { // 목표점에 모드 들어왔는지 확인
		int cnt = 0;
		for (int i = 0; i < list.size(); i++) {
			Node n = list.get(i);
			if(map[n.y][n.x] == 'b') 
				cnt++;
		}
		if(cnt == list.size())
			return true;
		else
			return false;
	}

	
	private static void move(int n) {
		int ny = sy + dy[n];
		int nx = sx + dx[n];
		if(map[ny][nx] == '.') { // 가려는 곳이 이동가능하면 좌표값 갱신
			sy = ny;
			sx = nx;
		}else if(map[ny][nx] == 'b') { // 가려는 곳이 박스면 그다음 까지 체크
			int nny = ny + dy[n];
			int nnx = nx + dx[n];
			if(map[nny][nnx] == '.') { // 그다음 가려는 곳이 이동가능하면 싹 이동시킴
				map[nny][nnx] = 'b';
				map[ny][nx] = '.';
				sy = ny;
				sx = nx;
			}
		}
	}

	static class Node{
		int y, x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드