[백준] 16197 두 동전 - 파이썬

문제

 

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

16197번: 두 동전

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

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

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

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

입력

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

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

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

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

출력

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

 

 

---

풀이

 

10번 제한이 걸려있길래 bfs로 풀었다.

1번 동전이 떨어질 때, 2번 동전이 떨어질 때, 동전 두 개가 동시에 떨어질 때의 조건 처리를 잘 해주면 될 것 같았다.

그런데 시간초과 발생!

 

설마 했는데 방문처리를 해줘야 하는 듯 하다.

생각해보니 n, m이 20 이하인 조건이 있기때문에 4차원 배열을 만들어도 크게 공간을 차지하지 않았다.

 

그래서 동전1y값 1x값, 2y, 2x값을 저장하는 4차원 배열 visited를 만들어 방문처리를 해줬는데도 시간초과 발생

 

다른 사람 글을 봐도 로직 자체는 정말 똑같은 것 같은데 어디서 시간초과가 발생하는지 모르겠다..

pypy3로 바꾸니 틀렸습니다로 바뀌었다

무언가 조건문 처리 잘못한듯? 

 

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(input())[:-1] for _ in range(n)]

coins = []
for i in range(n):
    for j in range(m):
        if board[i][j] == 'o':
            coins.append((i,j))
            board[i][j] = '.'

q = deque([(coins[0], coins[1], 0)])
visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
visited[q[0][0][0]][q[0][0][1]][q[0][1][0]][q[0][1][1]] = True

dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]
while q:
    c1, c2, t = q.popleft()
    if t > 10:
        print(-1)
        exit(0)
    for d in dir:
        dropped = False
        c1y = c1[0]+d[0]
        c1x = c1[1]+d[1]
        c2y = c2[0]+d[0]
        c2x = c2[1]+d[1]
        if (c1x < 0 or c1x >= m) or (c1y < 0 or c1y >= n):
            dropped = True
        if (c2x < 0 or c2x >= m) or (c2y < 0 or c2y >= n):
            if not dropped:
                print(t+1)
                exit(0)
            else:
                continue
        if dropped:
            print(t+1)
            exit(0)
        if board[c1y][c1x] == '#':
            c1y = c1[0]
            c1x = c1[1]
        if board[c2y][c2x] == '#':
            c2y = c2[0]
            c2x = c2[1]
        if not (c1y == c2y and c2x == c2x) and not visited[c1y][c1x][c2y][c2x]:
            q.append(((c1y, c1x), (c2y, c2x), t+1))

 

이리저리 만져본 결과

while문 밖에 print(-1)을 추가하고 while문 안의 t >10 조건을 t >= 10으로 바꾸고 통과했다.

 

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(input())[:-1] for _ in range(n)]

coins = []
for i in range(n):
    for j in range(m):
        if board[i][j] == 'o':
            coins.append((i,j))
            board[i][j] = '.'

q = deque([(coins[0], coins[1], 0)])
visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
visited[q[0][0][0]][q[0][0][1]][q[0][1][0]][q[0][1][1]] = True

dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]
while q:
    c1, c2, t = q.popleft()
    if t > 10:
        print(-1)
        exit(0)
    for d in dir:
        c1y = c1[0]+d[0]
        c1x = c1[1]+d[1]
        c2y = c2[0]+d[0]
        c2x = c2[1]+d[1]
        if (0 <= c1x < m) and (0 <= c1y < n) and (0 <= c2x < m) and (0 <= c2y < n):
            if board[c1y][c1x] == '#':
                c1y, c1x = c1[0], c1[1]
            if board[c2y][c2x] == '#':
                c2y, c2x = c2[0], c2[1]
            if (not (c1y == c2y and c2x == c2x)) and not visited[c1y][c1x][c2y][c2x]:
                q.append(((c1y, c1x), (c2y, c2x), t + 1))
        elif (0 <= c1x < m) and (0 <= c1y < n):
            print(t+1)
            exit(0)
        elif (0 <= c2x < m) and (0 <= c2y < n):
            print(t+1)
            exit(0)
print(-1)