[백준 - Python] 16197 - 두 동전

0.  문제 링크

 

 

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

16197번: 두 동전

---

1.  풀이 방법

 

 

첫 번째로 동전의 위치를 찾았다.

만약 동전이 둘 다 범위 안에 있다면, 무난하게 동전을 움직이게 했고, 만약 벽이라면 움직이지 않고 다시 현재 위치에 있게 했다.

그리고 다시 deque에 넣었다.

만약 동전이 둘 다 범위 바깥이라면, 둘 다 떨어졌다는 의미이므로, continue를 했다.

만약 한 개만 떨어졌다면 그대로 반환을 했음

 

하지만 해당 경우에 동전이 겹치는 경우는 따로 처리하지 않았는데, 어차피 동전이 겹치면 둘 다 떨어지거나, 둘 다 떨어지지 않거나 둘 중 하나기 때문에 처리하지는 않았다.

---

2.  코드

 

 

from collections import deque


def bfs():
    while dq:
        y1, x1, y2, x2, cnt = dq.popleft()
        if cnt >= 10:
            return -1
        for dy, dx in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            ny1, nx1 = y1 + dy, x1 + dx
            ny2, nx2 = y2 + dy, x2 + dx
            if 0 <= ny1 < n and 0 <= nx1 < m and 0 <= ny2 < n and 0 <= nx2 < m:
                if maps[ny1][nx1] == '#':
                    ny1, nx1 = y1, x1
                if maps[ny2][nx2] == '#':
                    ny2, nx2 = y2, x2
                dq.append([ny1, nx1, ny2, nx2, cnt + 1])
            elif not (0 <= ny1 < n and 0 <= nx1 < m) and not(0 <= ny2 < n and 0 <= nx2 < m):
                continue
            else:
                return cnt + 1
    return -1


if __name__ == "__main__":
    n, m = map(int, input().split())
    maps = [list(input()) for _ in range(n)]
    tp = []
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'o':
                tp.append(i)
                tp.append(j)
    dq = deque()
    dq.append([*tp, 0])

    print(bfs())

 

---

3.  마무리