[파이썬] 백준 3197 : 백조의 호수 (플레5)

[파이썬] 백준 3197 : 백조의 호수 (플레5)

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

---

풀이

방향성 생각

• BFS + 유니온파인드.

• 첫 BFS를 돌리고, 각 분리된 영역마다 번호를 매긴다. BFS를 돌리면서 X와 닿는 부분을 Q에 넣는다.

  • 백조가 있는 곳을 우선으로 1,2.

  • 그 이후부터는 3,4, ...로 매긴다.

  • 유니온 시, 루트 노드를 작은 쪽으로 해서 백조1과 백조2가 합쳐질 때 시그널을 받기 위함.

• Q넣은 좌표들을 주변으로 spread 시킨다.

  • spread 시키며 다음 부분들은 next queue, nQ에 담는다.

---

전체코드

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

inside = lambda x,y: 0<=x<X and 0<=y<Y
dire = [(1,0),(0,1),(-1,0),(0,-1)]

Y,X = map(int,input().split())
arr = [list(input()) for _ in range(Y)]

# BFS를 돌리면서 V에 넘버링 + 방문처리를 진행한다.
V = [[0]*X for _ in range(Y)]
Q = deque() # 경계면과 닿는 애들의 좌표
def bfs(x,y,idx):
    V[y][x] = idx
    temp = deque([(x,y,idx)])
    while temp:
        x,y,idx = temp.popleft()

        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            if inside(nx,ny) and not V[ny][nx]: 
                if arr[ny][nx] == 'X':
                    Q.append((x,y,idx))
                else:                    
                    temp.append((nx,ny,idx)) # 백조 또는 물은 같은 영역
                    V[ny][nx] = idx

# 백조1, 백조2를 먼저 찾고 BFS 시킨다.
number = 1
swans_loc = []
for y in range(Y):
    for x in range(X):
        if arr[y][x] == 'L':
            swans_loc.append((x,y))
for x,y in swans_loc: # 백조가 같은 영역에 있는 경우 예외처리
    if not V[y][x]:
        bfs(x,y,number)
    number += 1

# 백조가 없는 경우 BFS
swans = []
for y in range(Y):
    for x in range(X):
        if arr[y][x] != 'X' and not V[y][x]:
            bfs(x,y,number)
            number += 1

        if arr[y][x] == 'L':
            swans.append(V[y][x])

# 유니온 파인드
P = [i for i in range(number+1)]
connected = False
def find(a):
    if P[a] != a:
        P[a] = find(P[a])
    return P[a]

def union(x,y):
    global connected
    px,py = find(x),find(y)
    if px != py:
        P[max(px,py)] = P[min(px,py)]
        if (px,py) == (1,2) or (px,py)==(2,1): # 영역의 루트노드가 1 2 또는 2 1일 경우 백조가 만난다.
            connected = True

# 얼음이 녹는 경우
def spread(Q):
    nQ = deque()
    while Q:
        x,y,idx = Q.popleft()
        V[y][x] = idx

        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            if inside(nx,ny) and not V[ny][nx]:
                V[ny][nx] = idx
                nQ.append((nx,ny,idx))

                # .X.의 경우 그냥 합쳐진다. .XX.의 경우, 도착지점 nx ny에서 인접노드 체크해줘야함.
                for ddx,ddy in dire:
                    nnx,nny = nx+ddx,ny+ddy
                    if inside(nnx,nny) and V[nny][nnx]:
                        union(idx,V[nny][nnx])
    return nQ

# 정답출력
answer = 0
if swans[0] == swans[1]:
    print(answer)
else:
    while True:
        Q = spread(Q)
        answer += 1
        if connected:
            print(answer)
            break

코멘트

• 1년 전쯤에 머리박으면서 풀다가 실패했던 문제.

• 블로그들 보면 대부분 큐 4갠가? 조금 발상적인 방식으로 접근했다.

• 이번에는 그냥 Spread에서 다다음노드 체크 잘 하는 방식으로 변경해서 원트컷.