[백준: Java] 4577 - 소코반

[문제]

https://www.acmicpc.net/problem/4577

조건에 맞춰 시뮬레이션을 수행하면 되는 단순한 문제입니다. 하지만 예외 처리 부분을 바로 떠올리지 못해 시간을 많이 잡아먹었던 문제입니다. 또한 게임이 끝났을 때 남은 명령을 수행하지 않는다는 것을 확인하지 못해 더 오래 걸렸습니다. 

---

[초기화]

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int r, c;
	static char[][] grid;
	static String command;
	static StringBuilder sb = new StringBuilder();
	static Map<Character, int[]> directions = Map.of(
			'U', new int[] {-1, 0}, 
			'D', new int[] {1, 0}, 
			'L', new int[] {0, -1}, 
			'R', new int[] {0, 1});
	
	public static void main(String[] args) throws IOException {
		int t = 0;
		while(true) {
			st = new StringTokenizer(br.readLine());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			if(r == 0 && c == 0)
				break;
			
			grid = new char[r][c];
			
			for(int i = 0; i < r; i++) {
				String line = br.readLine();
				for(int j = 0; j < c; j++) {
					grid[i][j] = line.charAt(j);
				}
			}
			
			command = br.readLine();
			
			sb.append("Game ").append(++t).append(": ").append(solve() ? "complete" : "incomplete").append("\n");
			for(char[] i: grid) {
				for(char j: i)
					sb.append(j);
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}

 

명령에 따라 이동해야 하므로 명령과 이동 방향을 Map으로 정의합니다.

---

[풀이]

	static class Player {
		char state, current;
		int y, x;
		
		Player(char state, char current, int y, int x) {
			this.state = state;  // 현재 상태
			this.current = current;  // 현재 위치한 공간
			this.y = y;
			this.x = x;
		}
	}

플레이어를 나타낼 클래스를 정의하였습니다. 그리드 상에 표현되는 플레이어의 모습과, 플레이어가 현재 위치한 공간을 저장합니다.

 

현재 위치한 공간을 저장하는 이유는, 플레이어를 이동시킬 때 플레이어가 있던 공간을 원래대로 되돌리기 위함입니다.

	static Player search_chracter() {
		int y = 0, x = 0;
		loop: for(int i = 0; i < r; i++)
			for(int j = 0; j < c; j++)
				if(grid[i][j] == 'w' || grid[i][j] == 'W') {
					y = i;
					x = j;
					break loop;
				}
		
		char current = grid[y][x] == 'w' ? '.' : '+';
		return new Player(grid[y][x], current, y, x);
	}

플레이어의 위치를 찾습니다. 주의할 점은 플레이어가 빈 공간에 위치할 수도 있지만 목표점에 위치할 수도 있기 때문에 두 경우를 고려해야 합니다.

 

찾아낸 플레이어의 상태에 따라 현재의 공간 정보를 저장합니다.

 

w인 경우 빈 공간을, W인 경우 목표점을 저장하게 됩니다.

	static int count_target() {
		int target = 0;
		
		for(int i = 0; i < r; i++)
			for(int j = 0; j < c; j++)
				if(grid[i][j] == '+' || grid[i][j] == 'W')  // 모든 목표점에 대해
					target++;
		
		return target;
	}

그리드에 위치한 목표점이 몇 개인지 확인합니다.

 

이는 시뮬레이션이 끝났을 때, 목표를 달성했는지 아닌지를 확인하는 동시에 목표를 달성했을 경우 남은 명령을 수행하지 않기 위함입니다.

	static void move_player(Player player, int my, int mx, char next_point) {
		grid[player.y][player.x] = player.current;  // 플레이어가 있던 자리 원상 복귀
		
		player.current = grid[my][mx];  // 이동한 곳의 공간
		player.state = grid[my][mx] == next_point ? 'W' : 'w';
        
		player.y = my;
		player.x = mx;
		grid[my][mx] = player.state;  // 플레이어 이동
	}

플레이어를 이동시킵니다.

1. 현재 위치를 플레이어가 아닌 원래 모습으로 되돌립니다.
2. 플레이어의 현재 위치를 이동하려는 곳으로 변경합니다. 또한 이에 따라 상태도 상태로 변경합니다.
   1. 고려 가능한 경우는 빈 공간(.)과 목표점(+) 일 때입니다.
      
      • 빈 공간이라면 기본 모습으로 돌립니다. 빈 공간이 아니라면 이동 가능한 공간은 목표점인 경우입니다.
3. 좌표적으로 플레이어를 이동시킵니다.
4. 그리드 상에 실제 플레이어를 반영합니다.

	static boolean move(Player player) {
		int len = command.length();
		int target = count_target();
		
		for(int i = 0; i < len; i++) {
			char c = command.charAt(i);
			int[] d = directions.get(c);
			
			int my = player.y + d[0];
			int mx = player.x + d[1];
			if(0 <= my && my < r && 0 <= mx && mx < c) {  // 유효 범위라면
				if(grid[my][mx] == '#')  // 벽이면 이동 불가
					continue;
				// 풀이 로직
			}
		}
		
		return false;
	}

주어진 명령을 하나씩 가져와서 다음 이동 방향을 결정합니다. 가고자 하는 방향이 유효하다면 움직임을 수행합니다.

 

이동하려는 곳이 벽이라면 움직임을 생략합니다.

 

움직이는 과정에서 목표를 달성하지 못했다면 false를 반환합니다. 

				if(grid[my][mx] == '.' || grid[my][mx] == '+')
					move_player(player, my, mx, '.');

우선 이동하려는 곳에 벽돌이 없는 경우입니다.

1. 이동하는 곳이 벽인 경우 움직이지 않습니다.
2. 플레이어를 이동시킵니다.

				else {  // 벽돌인 경우
					int next_y = my + d[0];  // 벽돌을 옮길 위치
					int next_x = mx + d[1];
					
					if(0 <= next_y && next_y < r && 0 <= next_x && next_x < c) {
						if(grid[next_y][next_x] == '#' || grid[next_y][next_x] == 'b' || grid[next_y][next_x] == 'B')
							continue;
						
						if(grid[next_y][next_x] == '+') {  // 박스가 이동할 곳이 목표점이라면
							grid[next_y][next_x] = 'B';
							target--;  // 박스를 목표점에 옮겼으므로 하나 제거
						}
						else
							grid[next_y][next_x] = 'b';
						
						if(grid[my][mx] == 'B') {  // 목표점에 있는 박스를 옮겼으니 해당 자리는 목표점으로 원상 복귀
							grid[my][mx] = '+';
							target++;  // 목표점에 있던 상자가 위치를 벗어났으므로 하나 추가
						}
						else
							grid[my][mx] = '.';  // 목표점이 아니라면 빈 공간 밖에 없음
						
						move_player(player, my, mx, '+');
						
						if(target == 0)  // 현재 움직이 끝났을 때, 모든 박스를 옮겼다면 게임 즉시 종료
							return true;
					}
				}

이동하려는 곳이 벽돌인 경우입니다.

 

벽돌의 경우, 현재 방향에서 동일한 방향으로 한 번 더 밀어줘야 합니다.

 

마찬가지로 벽돌을 밀 곳이 유효해야 합니다.

 

1. 벽돌을 밉니다.
   1. 밀려는 곳이 목표점이라면 그곳의 상태를 변경하고 채워야 하는 목표점의 수를 감소시킵니다.
   2. 밀려는 것이 목표점이 아닐 경우 상태만 변경합니다.
2. 벽돌이 밀렸으니, 원래 벽돌이 있던 위치를 되돌립니다.
   1. 벽돌의 상태가 B였다면 그곳은 목표점이라는 의미이므로 목표점으로 상태를 변경합니다.
   2. 목표점에 있던 벽돌이 벗어났으므로 목표점의 수를 다시 증가시킵니다.
   3. B가 아니라면 목표점이 아니었다는 의미이므로 빈 공간으로 변경합니다.
3. 벽돌이 있던 곳으로 플레이어를 이동시킵니다.
4. 모든 이동이 끝났을 때 더 이상 채울 목표점이 없다면 함수를 종료시킵니다.

---

[전체 코드]

package 백준.골드;

import java.io.*;
import java.util.*;

public class BOJ_4577_소코반 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int r, c;
	static char[][] grid;
	static String command;
	static StringBuilder sb = new StringBuilder();
	static Map<Character, int[]> directions = Map.of(
			'U', new int[] {-1, 0}, 
			'D', new int[] {1, 0}, 
			'L', new int[] {0, -1}, 
			'R', new int[] {0, 1});
	
	public static void main(String[] args) throws IOException {
		int t = 0;
		while(true) {
			st = new StringTokenizer(br.readLine());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			if(r == 0 && c == 0)
				break;
			
			grid = new char[r][c];
			
			for(int i = 0; i < r; i++) {
				String line = br.readLine();
				for(int j = 0; j < c; j++) {
					grid[i][j] = line.charAt(j);
				}
			}
			
			command = br.readLine();
			
			sb.append("Game ").append(++t).append(": ").append(solve() ? "complete" : "incomplete").append("\n");
			for(char[] i: grid) {
				for(char j: i)
					sb.append(j);
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}
	
	static Player search_chracter() {
		int y = 0, x = 0;
		loop: for(int i = 0; i < r; i++)
			for(int j = 0; j < c; j++)
				if(grid[i][j] == 'w' || grid[i][j] == 'W') {
					y = i;
					x = j;
					break loop;
				}
		
		char current = grid[y][x] == 'w' ? '.' : '+';
		return new Player(grid[y][x], current, y, x);
	}
	
	static int count_target() {
		int target = 0;
		
		for(int i = 0; i < r; i++)
			for(int j = 0; j < c; j++)
				if(grid[i][j] == '+' || grid[i][j] == 'W')  // 모든 목표점에 대해
					target++;
		
		return target;
	}
	
	static void move_player(Player player, int my, int mx, char next_point) {
		grid[player.y][player.x] = player.current;  // 플레이어가 있던 자리 원상 복귀
		
		player.current = grid[my][mx];  // 이동한 곳의 공간
		player.state = grid[my][mx] == next_point ? 'W' : 'w';
        
		player.y = my;
		player.x = mx;
		grid[my][mx] = player.state;  // 플레이어 이동
	}

	static boolean move(Player player) {
		int len = command.length();
		int target = count_target();
		
		for(int i = 0; i < len; i++) {
			char c = command.charAt(i);
			int[] d = directions.get(c);
			
			int my = player.y + d[0];
			int mx = player.x + d[1];
			if(0 <= my && my < r && 0 <= mx && mx < c) {  // 유효 범위라면
				if(grid[my][mx] == '#')  // 벽이면 이동 불가
					continue;
				
				if(grid[my][mx] == '.' || grid[my][mx] == '+')
					move_player(player, my, mx, '.');
				else {  // 벽돌인 경우
					int next_y = my + d[0];  // 벽돌을 옮길 위치
					int next_x = mx + d[1];
					
					if(0 <= next_y && next_y < r && 0 <= next_x && next_x < c) {
						if(grid[next_y][next_x] == '#' || grid[next_y][next_x] == 'b' || grid[next_y][next_x] == 'B')
							continue;
						
						if(grid[next_y][next_x] == '+') {  // 박스가 이동할 곳이 목표점이라면
							grid[next_y][next_x] = 'B';
							target--;  // 박스를 목표점에 옮겼으므로 하나 제거
						}
						else
							grid[next_y][next_x] = 'b';
						
						if(grid[my][mx] == 'B') {  // 목표점에 있는 박스를 옮겼으니 해당 자리는 목표점으로 원상 복귀
							grid[my][mx] = '+';
							target++;  // 목표점에 있던 상자가 위치를 벗어났으므로 하나 추가
						}
						else
							grid[my][mx] = '.';  // 목표점이 아니라면 빈 공간 밖에 없음
						
						move_player(player, my, mx, '+');
						
						if(target == 0)  // 현재 움직이 끝났을 때, 모든 박스를 옮겼다면 게임 즉시 종료
							return true;
					}
				}
			}
		}
		
		return false;
	}
	
	static boolean solve() {
		Player player = search_chracter();  // 플레이어 위치 탐색
		return move(player);  // 플레이어 이동
	}
	
	static class Player {
		char state, current;
		int y, x;
		
		Player(char state, char current, int y, int x) {
			this.state = state;  // 현재 상태
			this.current = current;  // 현재 위치한 공간
			this.y = y;
			this.x = x;
		}
	}
}

---