문제

BOJ 4577: 소코반 https://www.acmicpc.net/problem/4577

풀이

조건

• 박스를 밀어서 목표지점까지 옮기는 게임과 같은 규칙이다.
• 플레이어는 화살표(위, 아래, 왼쪽, 오른쪽)를 이용해 캐릭터를 아래와 같은 규칙으로 조정할 수 있다.
  • 캐릭터에게 지시한 방향이 빈 칸(박스나 벽이 아닌 곳)인 경우에는 그 칸으로 이동한다.
  • 지시한 방향에 박스가 있는 경우에는, 박스를 민다. 이 경우에는 박스가 이동할 칸도 비어있어야 한다.
  • 지시한 방향이 벽인 경우, 또는 박스가 있는데, 박스가 이동할 칸에 다른 박스나 벽이 있는 경우에는 키를 눌러도 캐릭터는 이동하지 않는다.
• 모든 박스를 목표점으로 이동시킨 경우에 게임은 끝난다. 게임이 끝난 후에 입력하는 키는 모두 무시된다.
• 위, 아래, 왼쪽, 오른쪽은 U, D, L, R로 나타낸다.
• 입력의 마지막 줄에는 0 0이 주어진다.
• 항상 캐릭터가 한 명이고, 박스의 수와 목표점의 수는 같다.
• 목표점 위에 올라가 있지 않은 박스는 적어도 한 개 이며, 가장 바깥쪽 칸은 항상 벽이다.
• 게임의 상태는 아래와 같은 문자로 나타낼 수 있다.
  

풀이 순서

• 게임을 시작하자마자 종료되는지 체크한다.
  • 종료 가능하면 게임 라운드 +1 해주고 다음 게임으로 넘어간다.
• 명령을 차례로 수행한다.
  • 명령이 끝나기 전에 게임이 끝날 수 있으면 게임 라운드 +1 해주고 다음 라운드로 넘어간다.
• 모든 명령이 끝날 때 까지 게임이 끝나지 않으면 마지막 상태를 출력한다.
• 박스를 밀 땐 박스가 밀리는 위치가 빈칸이거나 목표위치인지 체크해준다.
• 함수를 적절히 만들면 풀기 쉽다.

코드

Python

import sys


# 다음 위치가 박스인지 확인하는 함수
def is_next_box(nxt_x, nxt_y):
    if board[nxt_x][nxt_y] in ['b', 'B']:
        return True
    return False


# 다음 위치가 목표위치인지 확인하는 함수
def is_next_goal_pos(nxt_x, nxt_y):
    global goal_pos
    if [nxt_x, nxt_y] in goal_pos:
        return True
    return False


# 박스를 밀 수 있는지 확인하는 함수
def can_push_box(box_x, box_y, cmd):
    global board
    nxt_box_x = box_x
    nxt_box_y = box_y
    # 박스를 밀면 어느 위치로 가는지 탐색
    if cmd == 'U':
        nxt_box_x = box_x - 1
        nxt_box_y = box_y
    elif cmd == 'D':
        nxt_box_x = box_x + 1
        nxt_box_y = box_y
    elif cmd == 'L':
        nxt_box_x = box_x
        nxt_box_y = box_y - 1
    elif cmd == 'R':
        nxt_box_x = box_x
        nxt_box_y = box_y + 1
    # 박스가 밀리는 위치가 벽이거나 다른 박스가 있으면 
    # False 반환
    if board[nxt_box_x][nxt_box_y] in ['b', 'B', '#']:
        return False, -1, -1
    # 박스를 밀수 있으면
    # True와 박스가 밀린 뒤의 위치를 반환
    return True, nxt_box_x, nxt_box_y


# 명령에 따라 플레이어가 움직이는 함수
def move(now_player_pos, cmd):
    global board
    now_x = now_player_pos[0]
    now_y = now_player_pos[1]

    nxt_x, nxt_y = now_x, now_y
    # 명령에 따라 다음 위치 확인
    if cmd == 'U':
        nxt_x = now_x - 1
        nxt_y = now_y
    elif cmd == 'D':
        nxt_x = now_x + 1
        nxt_y = now_y
    elif cmd == 'L':
        nxt_x = now_x
        nxt_y = now_y - 1
    elif cmd == 'R':
        nxt_x = now_x
        nxt_y = now_y + 1

    # 벽인지 확인
    if board[nxt_x][nxt_y] == '#':
        # 제자리에 있음
        return [now_x, now_y]

    # 다음 위치가 박스가 아니라면
    if not is_next_box(nxt_x, nxt_y):
        # 플레이어가 이동할 위치가 목표지점이면 W로 전환하고 이동
        if is_next_goal_pos(nxt_x, nxt_y):
            board[nxt_x][nxt_y] = 'W'
            board[now_x][now_y] = '.'
            return [nxt_x, nxt_y]
        # 그냥 빈공간이면 그냥 이동
        else:
            board[nxt_x][nxt_y] = 'w'
            board[now_x][now_y] = '.'
            return [nxt_x, nxt_y]
    # 다음 위치가 박스 라면
    else:
        # 박스를 밀 수 있는지 확인
        check_box_push, nxt_box_x, nxt_box_y = can_push_box(nxt_x, nxt_y, cmd)
        # 박스 못 밀면 종료
        if not check_box_push:
            # 못 밀기 때문에 제자리에 있음
            return [now_x, now_y]
        # 박스 밀 수 있으면 밂
        else:
            # 박스 미는 위치가 목표 위면
            if is_next_goal_pos(nxt_box_x, nxt_box_y):
                # 박스 B로 전환
                board[nxt_box_x][nxt_box_y] = 'B'
                # 플레이어도 목표 위인지 체크
                if is_next_goal_pos(nxt_x, nxt_y):
                    board[nxt_x][nxt_y] = 'W'
                    board[now_x][now_y] = '.'
                else:
                    board[nxt_x][nxt_y] = 'w'
                    board[now_x][now_y] = '.'
            # 박스 미는 위치가 그냥 빈공간이면
            else:
                # 그냥 밂
                board[nxt_box_x][nxt_box_y] = 'b'
                # 플레이어도 목표 위인지 체크
                if is_next_goal_pos(nxt_x, nxt_y):
                    board[nxt_x][nxt_y] = 'W'
                    board[now_x][now_y] = '.'
                else:
                    board[nxt_x][nxt_y] = 'w'
                    board[now_x][now_y] = '.'
            return [nxt_x, nxt_y]


# 게임이 끝날 수 있는지 확인하는 함수
def is_complete(goal_pos):
    box_pos = []
    for r in range(R):
        for c in range(C):
            # 현재 박스들의 위치 저장
            if board[r][c] in ['B', 'b']:
                box_pos.append([r, c])
            # 목표 위치인데 위에 아무것도 없으면 '+'표시 해줌
            if [r, c] in goal_pos and board[r][c] not in ['B', 'b', 'w', 'W']:
                board[r][c] = '+'

    # 목표 위치 위에 모든 박스가 올라가있는지 확인
    for box in box_pos:
        if box not in goal_pos:
            return False

    return True


game_cnt = 1
while True:
    R, C = map(int, sys.stdin.readline().rstrip().split())

    if R == 0 and C == 0:
        break

    # 게임 화면
    board = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
    # 이동 명령
    commands = list(sys.stdin.readline().rstrip())

    # 플레이어 위치, 목표 위치 저장
    player_pos = []
    goal_pos = []
    for i in range(R):
        for j in range(C):
            if board[i][j] in ['w', 'W']:
                player_pos = [i, j]
            if board[i][j] in ['+', 'B', 'W']:
                goal_pos.append([i, j])

    # 처음부터 게임이 종료될 수 있는지 확인
    end_flag = False
    if is_complete(goal_pos):
        print(f'Game {game_cnt}: complete')
        for i in range(R):
            for j in range(C):
                print(board[i][j], end='')
            print()
        end_flag = True
    if end_flag:  # 종료 될 수 있으면 바로 다음 케이스로 넘어감
        game_cnt += 1  # 게임 라운드 +1
        continue

    # 명령들 차례로 수행
    end_flag = False
    for command in commands:
        player_pos = move(player_pos, command)
        # 종료될 수 있는지 체크
        if is_complete(goal_pos):
            print(f'Game {game_cnt}: complete')
            for i in range(R):
                for j in range(C):
                    print(board[i][j], end='')
                print()
            end_flag = True
            break

    if end_flag:  # 종료 될 수 있으면 바로 다음 케이스로 넘어감
        game_cnt += 1  # 게임 라운드 +1
        continue

    # 게임 완료가 끝까지 안되면 incomplete 출력하고 다음 케이스로
    print(f'Game {game_cnt}: incomplete')
    for i in range(R):
        for j in range(C):
            print(board[i][j], end='')
        print()

    game_cnt += 1  # 게임 라운드 +1

정리

• 게임이 중간에 종료될 때 라운드 번호 +1 해주는 부분을 빼먹어서 틀렸었다.
• 잘 체크하자..