백준 16197번 - 두 동전(★★★ / ▲ / 1) : Python

개요

• 풀이 시간 : 30분
• 시간 제한 : 2초
• 메모리 제한 : 512 MB
• 기출 : baekjoon
• 링크 : https://www.acmicpc.net/problem/16197

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

해결방법

문제 이해하기

처음 문제를 보고 음... 이것도 그래프 탐색이라서 쉽겠네? 라고 생각했는데 막상 생각하는 시간이 길었다. 왜냐하면 동전 두개를 BFS를 통해 이동시킨다면 중복방문을 막기위해 방문처리를 어떻게 처리할지가 문제였다.

알고리즘

사실 이 문제에서는 방문처리를 굳이 할 필요는 없었다. 왜냐면 버튼을 10번보다 많이 눌러야 한다면, -1을 출력해주면 되기 때문이다. 즉, 4(상하좌우)^10을 계산해봤을때 1,048,576이 나오므로 시간초과없이 해결할 수 있긴하다.

다만 방문처리를 할 수 있는 방법이 없지는 않다. 바로 4차원 배열을 만드는 방법이다.

visited = [[[[False for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]

visited[x1][y1][x2][y2] = True

Python

내 코드

from collections import deque
import sys

input = sys.stdin.readline

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def bfs():
    while coin:
        x1, y1, x2, y2, cnt = coin.popleft()

        if cnt >= 10:
            return -1

        for i in range(4):
            nx1 = x1 + dx[i]
            ny1 = y1 + dy[i]
            nx2 = x2 + dx[i]
            ny2 = y2 + dy[i]

            if 0 <= nx1 < n and 0 <= ny1 < m and 0 <= nx2 < n and 0 <= ny2 < m:
                # 벽이라면
                if board[nx1][ny1] == "#":
                    nx1, ny1 = x1, y1
                if board[nx2][ny2] == "#":
                    nx2, ny2 = x2, y2
                coin.append((nx1, ny1, nx2, ny2, cnt + 1))
            elif 0 <= nx1 < n and 0 <= ny1 < m:  # coin2가 떨어진 경우
                return cnt + 1
            elif 0 <= nx2 < n and 0 <= ny2 < m:  # coin1가 떨어진 경우
                return cnt + 1
            else:  # 둘 다 빠진 경우 무시
                continue

    return -1


if __name__ == "__main__":
    n, m = map(int, input().split())

    coin = deque()
    board = []
    temp = []
    for i in range(n):
        board.append(list(input().strip()))
        for j in range(m):
            if board[i][j] == "o":
                temp.append((i, j))

    coin.append((temp[0][0], temp[0][1], temp[1][0], temp[1][1], 0))

    print(bfs())

추천 코드

💻 참고 : https://www.acmicpc.net/source/26550015

이렇게 하는게 메모리나 시간측면에서 내 코드보다 효율성이 좋았다.