개발조아

[BOJ/백준] 4577 소코반 파이썬 본문

알고리즘/백준

[BOJ/백준] 4577 소코반 파이썬

개발조아 2021. 9. 19. 23:28
728x90

문제 링크 : https://www.acmicpc.net/problem/4577

 

4577번: 소코반

소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수

www.acmicpc.net

 

요구하는 사항이 어렵지는 않지만 체크해줘야할 게 많은 문제이다.

졸려서 문제를 대충 읽었다가 몇번 틀렸다.

 

캐릭터가 이동하는 방향이 .이거나+ 라면 그대로 이동하면 된다.

근데 b 라면 다음칸도 확인해서 .이거나+ 라면 캐릭터와 블록을 각 한칸씩 이동한다.

만약 박스를 목표지점에 다 넣었을 때는 다음 명령은 무시해도된다.

모든 명령을 수행후 결과를 출력하면 된다.

 

요구사항은 적다.

근데 캐릭터와 박스가 목표지점에서 시작할때와 블록이 이동하면서 목표지점에서 일반 지점으로 이동할때를 체크해줘야한다.

 

일단 나는 나는 맵정보를 입력받을 때 박스의 전체 개수(total_box_cnt)와 목표지점에 있는 박스 개수(now_box_cnt)를 세주었다.

그리고 캐릭터의 경우 시작 위치만 저장하고 소문자면 . 으로 바꿔주고, 만약 대문자라면 +로 바꾸고 dest라는 목표지점 변수에 좌표를 저장했다.

 

그리고 +라면 dest에 좌표를 저장했다.

 

다음 시뮬레이션을 돌리자. 이때 total_box_cnt와 now_box_cnt도 같이 넘겨줬다.

일단 모든 명령어를 수행하자.

근데 만약 total_box_cnt == now_box_cnt라면 반복문을 그만돌자.

문제에 모든 박스가 목표지점에 도달했다면 다음 명령어는 무시한다고 했기 때문이다.

 

다음 일단 요구사항 대로 움직이자.

다음칸이 .이거나 +라면 그냥 캐릭터 좌표만 수정하자.

 

만약 b나 B라면 박스이므로 다음칸도 확인하자.

만약 다음칸이 .이거나 +라면 박스를 옮겨주는데 만약 다음칸이 + 라면 now_box_cnt를 1 증가시키자.

그리고 박스의 원래 위치가 dest에 있는 좌표, 즉 목표 지점이라면 박스는 목표지점에서 벗어난 것이다.

그렇기 때문에 now_box_cnt를 1을 빼주자.

마지막으로 캐릭터의 좌표도 수정해주자.

 

반복문을 다 돌았다면 맵에 현재 캐릭터 위치에 w 를 넣어주자

그리고 now_box_cnt를 리턴해주고 만약 이 값이 total_box_cnt와 같다면 게임이 끝난 것이다.

 

마지막으로 게임의 최종맵 출력이다.

 

전체 칸을 돌면서 좌표가 dest에 포함되고 알파벳이라면 목표지점에 도달한 캐릭터거나 박스이다.

그러므로 대문자로 바꿔서 출력하자.

아니라면 그냥 출력하면 된다.

 

from sys import stdin

input = stdin.readline
dir = {
    'U':[-1,0],
    'D':[1,0],
    'L':[0,-1],
    'R':[0,1]
}

def solv():
    tc = 1
    while True:
        r,c = map(int, input().split())
        if r == 0 and c == 0:
            break

        sx=sy=-1
        dest = []
        board = []
        total_box_cnt = 0
        now_box_cnt = 0
        for x in range(r):
            board.append(list(input().strip()))
            for y in range(c):
                if board[x][y] == 'w':
                    sx,sy = x,y
                    board[x][y] = '.'
                elif board[x][y] == 'W':
                    sx,sy = x,y
                    dest.append((x,y))
                    board[x][y] = '+'
                elif board[x][y] == 'b':
                    total_box_cnt += 1
                elif board[x][y] == 'B':
                    total_box_cnt += 1
                    now_box_cnt += 1
                    dest.append((x,y))
                elif board[x][y] == '+':
                    dest.append((x,y))

        order = list(input().strip())
        now_box_cnt = simul(sx,sy,board,order,dest,total_box_cnt,now_box_cnt)
        if now_box_cnt == total_box_cnt:
            answer = 'complete'
        else:
            answer = 'incomplete'
        print('Game %d: %s' % (tc, answer))
        print_answer(board,dest,r,c)
        tc += 1
        
def print_answer(board,dest,r,c):
    for x in range(r):
        for y in range(c):
            if (x,y) in dest and board[x][y].isalpha():
                print(board[x][y].upper(), end='')
            else:
                print(board[x][y], end='')
        print()

def simul(x,y,board,order,dest,total_box_cnt,now_box_cnt):
    for op in order:
        if now_box_cnt == total_box_cnt:
            break
        nx = x + dir[op][0]
        ny = y + dir[op][1]

        if board[nx][ny] in '.+':
            x,y = nx,ny
        elif board[nx][ny] in 'bB':
            nnx = nx + dir[op][0]
            nny = ny + dir[op][1]
            if board[nnx][nny] in '.+':
                if board[nnx][nny] == '+':
                    now_box_cnt += 1
                board[nx][ny],board[nnx][nny] = '.','b'
                if (nx,ny) in dest:
                    board[nx][ny] = '+'
                    now_box_cnt -= 1
                x,y=nx,ny
    board[x][y] = 'w'
    return now_box_cnt
solv()
Comments