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

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

 

# 두 동전
import copy
from collections import deque
N, M = map(int, input().split())
arr = []
money = deque()
for i in range(N):
    arr.append(list(input().strip()))
    for j in range(M):
        if arr[i][j] == 'o':
            money.append((i, j))
            arr[i][j] = '.'

visited = set()
visited.add(''.join(map(str, money)))

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


def bfs():
    q = deque()
    q.append((0, money))
    while q:
        cnt, now = q.popleft()
        if cnt >= 10:
            return -1
        for k in range(4):
            # now를 깊은 복사
            temp = copy.deepcopy(now)
            # 동전의 개수는 두개
            for _ in range(2):
                x, y = temp.popleft()
                nx = x+dx[k]
                ny = y+dy[k]
                if 0 <= nx < N and 0 <= ny < M:
                    # . => 변한 값 append
                    if arr[nx][ny] == '.':
                        temp.append((nx, ny))
                    # # => 기존 값 append
                    elif arr[nx][ny] == '#':
                        temp.append((x, y))
            # 동전 개수가 1개이면 종료
            if len(temp) == 1:
                return cnt+1
            # 동전 개수가 0개이면 continue
            elif not temp:
                continue
            # 동전 개수가 2개이면 visited추가 & q.append
            visit = ''.join(map(str, temp))
            if visit not in visited:
                visited.add(visit)
                q.append((cnt+1, temp))
    return -1


print(bfs())

 

BFS
1. 입력을 받으면서 동전의 위치를 기록, o를 .으로 바꿔주기
2. visited를 집합으로 선언, 초기 동전 위치를 문자열로 추가
3. bfs
    - 이동횟수(cnt), 동전위치(now)를 q에서 관리
    - 4개의 이동방향마다 now를 깊은 복사
    - 2개의 동전을 이동
    - 이동 완료 후, 동전의 개수가 2개라면 visited 추가 & q에 append (둘 다 떨어졌을 경우에는 continue)
    - 이동 횟수가 10보다 크거나 이동이 불가능하면 -1 리턴
4. bfs 결과 출력

 

visited 관리가 핵심이라고 생각했다.

두 동전의 좌표를 문자열로 join해서 집합으로 관리했다.

집합에는 내부적으로 해시 테이블이 있어서 검색의 시간 복잡도는 O(1)이다.

not in 연산을 신경 썼다.

 

오른쪽 사진은 두 번째 예제의 visited의 값이다.

처음엔 '0010', '2020'과 같이 순수 좌표 값으로 설정하려고 했으나

그게 그거라 간단하게 join을 통해서 문자열로 만들었다.

 

그다음 중요한 것은 동전 2개에 대한 이동이라고 생각한다.

깊은 복사를 통해 동전의 처음 위치를 기억하고

기존 값과 변한 값을 상황에 따라 적절히 추가해주어야 한다.

deque로 관리하여 왼쪽부터 pop하고 오른쪽으로 추가해주는 작업으로

섞이는 것을 방지했다.