[파이썬] 백준 28032: Filed Day (플레2)

[파이썬] 백준 28032 : Filed Day (플레2)

• https://www.acmicpc.net/problem/28032

 

---

풀이

방향성 생각

• 입력이 커서 $O(N^2)$로는 불가능.
• 각 node bit로 표현하기.
• 주어진 node 중, 해당 node의 hamming dist를 찾기.
• 어떤 이진수 x가 있을 때, 각 자리를 모두 토글한 y는 x와 가장 해밍 거리를 가짐.
• x와 그 토글 y, 다른 node z가 있다고 가정하자.
• x -> z -> y 이동하는 경우 C만큼 걸림.
• 각 Node마다 BFS를 돌리면 시간 초과지만, 각 node의 toggle값을 넣고 BFS를 돌리면 해당 노드에서 가장 가까운 거리를 찾고 C에서 빼면 정답을 구할 수 있다.

---

전체코드

from collections import deque

W,H = map(int, input().split())

V = [-1]*(1<<W)
Q = deque()
arr = []
limit = 2**W-1
for _ in range(H):
    string = input()
    x = 0
    for idx,s in enumerate(string):
        x += (s=='G')*(2**idx)
    arr.append(x)
    V[limit-x] = 0
    Q.append(limit-x)

while Q:
    x = Q.popleft()
    for i in range(W):
        nx = x^(1<<i)
        if V[nx] == -1:
            Q.append(nx)
            V[nx] = V[x] + 1

for i in range(H):
    print(W-V[arr[i]])

 

---

코멘트

• 증명은 몰?루