[Gold III] 소코반 - 4577

문제 링크

분류

구현(implementation), 시뮬레이션(simulation)

문제 설명

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

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

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

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

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

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

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

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

---

풀이

풀이 순서

• 입력을 통해서 종료가 되는지 먼저 판단한다.
• 첫 시작 지점을 찾는다.
  • 첫 시작 지점이 목표 지점에 있을지도 모른다.
• 목표 지점을 리스트에 저장해둔다.
  • 나중에 목표 지점에서 박스를 밀었다가 나둘 때 다시 B로 바꾸기 위해서 저장
• 규칙에 따라 캐릭터를 움직이며 Map을 갱신해준다.
  • 목표지점에 박스를 다 올려두면 그 즉시 종료한다.

코드 (Python)

game = 1
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    Map = [list(input()) for _ in range(n)]
    start = []
    goal = []
    
    # 시작 지점과 목표 지점 리스트에 저장
    for i in range(n):
        for j in range(m):
            if Map[i][j] == 'w' or Map[i][j] == 'W':
                start = [i, j]
            if Map[i][j] == '+' or Map[i][j] == 'W' or Map[i][j] == 'B':
                goal.append([i, j])
    command = list(input())
    
    # 상, 하, 좌, 우
    move = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
    x, y = start[0], start[1]
    
    # 규칙에 따라 진행
    for com in command:
        nx = x + move[com][0]
        ny = y + move[com][1]
        if Map[nx][ny] == '.' or Map[nx][ny] == '+':
            Map[x][y] = '.'
            if [nx, ny] in goal:
                Map[nx][ny] = 'W'
            else:
                Map[nx][ny] = 'w'
            x, y = nx, ny
        elif Map[nx][ny] == 'b' or Map[nx][ny] == 'B':
            if Map[nx + move[com][0]][ny + move[com][1]] == '.':
                Map[x][y] = '.'
                if [nx, ny] in goal:
                    Map[nx][ny] = 'W'
                else:
                    Map[nx][ny] = 'w'
                if [nx + move[com][0], ny + move[com][1]] in goal:
                    Map[nx + move[com][0]][ny + move[com][1]] = 'B'
                elif Map[nx + move[com][0]][ny + move[com][1]] != '#':
                    Map[nx + move[com][0]][ny + move[com][1]] = 'b'
                x, y = nx, ny

            elif Map[nx + move[com][0]][ny + move[com][1]] == '+':
                Map[x][y] = '.'
                if [nx, ny] in goal:
                    Map[nx][ny] = 'W'
                else:
                    Map[nx][ny] = 'w'
                if [nx + move[com][0], ny + move[com][1]] in goal:
                    Map[nx + move[com][0]][ny + move[com][1]] = 'B'
                elif Map[nx + move[com][0]][ny + move[com][1]] != '#':
                    Map[nx + move[com][0]][ny + move[com][1]] = 'b'
                x, y = nx, ny
               
        # 목표 지점에 박스를 다 올려두면 중지
        cnt = 0
        for i in Map:
            cnt += i.count('B')
        if cnt == len(goal):
            break
    # 출력
    for i in Map:
        if '+' in i:
            print(f'Game {game}: incomplete')
            break
    else:
        print(f'Game {game}: complete')
    game += 1
    for i in range(n):
        for j in range(m):
            print(Map[i][j], end='')
        print()
	

정리

• 첫 시작점이 목표지점에 있을 수 도 있다라는 예외가 있었음...
• 목표 지점에 다 올려두면 중지해야한다는 조건을 모르고 삽질함...
• 문제를 잘읽자....