[BOJ/백준] 3197 백조의 호수

# 3197번 Fail
 
import sys
def find(number):
    if parents[number] == number:
        return number
    parents[number] = find(parents[number])
    return parents[number]
 
def merge(root,child):
    parents[child] = root
 
def water_merge():
    while water:
        cx,cy = water.pop(0)
        flag = True
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]
            if 0<= nx <R and 0<= ny <C:
                if check_map[nx][ny] != -1 and check_map[nx][ny] != check_map[cx][cy]:
                    parentA = find(check_map[cx][cy])
                    parentB = find(check_map[nx][ny])
                    if parentA != parentB:
                        merge(parentA,parentB)
                        check_map[nx][ny] = parentA
                elif check_map[nx][ny] == -1 and flag:
                    melt_water.append((cx,cy))
                    flag = False
 
 
def water_melt():
    while melt_water:
        cx,cy = melt_water.pop(0)
        root = find(check_map[cx][cy])
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]
            if 0<= nx <R and 0<= ny <C:
                if check_map[nx][ny] == -1:
                    water.append((nx,ny))
                    check_map[nx][ny] = root        
 
R,C = map(int,input().split())
 
arr = [list(sys.stdin.readline()) for _ in range(R)]
check_map = [[-1]*C for _ in range(R)]
parents = [-1]*(R*C)
cnt = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
swan = []
water = []
for x in range(R):
    for y in range(C):
        if arr[x][y] == '.' or arr[x][y] == 'L':
            water.append((x,y))
            parents[cnt] = cnt
            check_map[x][y] = cnt
            cnt += 1
            if arr[x][y] == 'L':
                swan.append((x,y))
 
swan1 = swan[0]
swan2 = swan[1]
time = 0
melt_water = []
while water:
    water_merge()
    if find(check_map[swan1[0]][swan1[1]]) == find(check_map[swan2[0]][swan2[1]]):
        result = time
        break
    water_melt()
    time += 1
 
            
print(result)

처음 시도했던 실패버전이다.

 

이 방법은 물을 union find로 한 묶음으로 한뒤, 탐색을 해주는 방식으로 했다. 그러나 이 방식의 문제점은 각 time에 대해 전부다 백조가 연결되어있는지 확인해야 하므로, 시간이 초과가 되었다. 

 

 

import sys
from collections import deque
import time
def isconnent_swan(start,end,standard_time):
    global R,C
    visited = [[True] * C for _ in range(R)]
    stack = deque()
    stack.append((start[0],start[1]))
    visited[start[0]][start[1]] = False
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx <R and 0<= ny <C:
                if melt_time[nx][ny] <= standard_time and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny))
                    if nx == end[0] and ny == end[1]:
                        return True
 
    return False
 
 
def find_max_spend_time():
    global R,C
    while waters:
        x,y,time = waters.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < R and 0<= ny < C:
                if melt_time[nx][ny] == -1:
                    melt_time[nx][ny] = time + 1
                    waters.append((nx,ny,time+1))
    return time
R,C = map(int,input().split())
origins = [list(sys.stdin.readline()) for _ in range(R)]
melt_time = [[-1]*C for _ in range(R)]
waters = deque()
swans = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for x in range(R):
    for y in range(C):
        if origins[x][y] != 'X':
            waters.append((x,y,0))
            melt_time[x][y] = 0
            if origins[x][y] == 'L':
                swans.append((x,y))
 
 
max_time = find_max_spend_time()
min_time = 0
result = 0
while min_time <= max_time:
    mid_time = (min_time + max_time)//2
    if isconnent_swan(swans[0],swans[1],mid_time):
        answer = mid_time
        max_time = mid_time - 1
    else:
        min_time = mid_time + 1
 
print(answer)

두번째로 찾은 방법은 빙하가 녹는 시간을 미리 구해주는 것이다. BFS를 통해 각 빙하들이 녹는 시간들을 찾아주고, 이분탐색으로 시간을 줄여가면서 백조들끼리 연결되어있는지 구하는 것이다.

빙하가 녹는시간을 구해놓고, 기준시간보다 작거나 같을시에는 이동이 가능하다고 판별을 해주었다.

 

하지만 이 방법도 백조가 연결되어있는지 매번 BFS를 해야하므로, 실행시간이 오래걸리는 편이었다.

 

 

from collections import deque
import sys
R,C = map(int,input().split())
 
lake = [list(sys.stdin.readline()) for _ in range(R)]
waters = deque()
swans = []
water_chk = [[True] *C for _ in range(R)]
swan_chk = [[True] *C for _ in range(R)]
for x in range(R):
    for y in range(C):
        if lake[x][y] != 'X':
            waters.append((x,y))
            water_chk[x][y] = False
            if lake[x][y] == 'L':
                swans.append((x,y))
                lake[x][y] = '.'
start_swan,end_swan = swans
swans = deque()
swans.append(start_swan)
swan_chk[start_swan[0]][start_swan[1]] = False
times = 0
new_water = deque()
new_swans = deque()
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while True:
    while waters:
        x,y = waters.popleft()
        lake[x][y] = '.'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < R and 0<= ny <C:
                if lake[nx][ny] == 'X' and water_chk[nx][ny]:
                    new_water.append((nx,ny))
                    water_chk[nx][ny] = False
    while swans:
        x,y = swans.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <R and 0<=ny<C:
                if swan_chk[nx][ny]:
                    if lake[nx][ny] == '.':
                        swans.append((nx,ny))
                    elif lake[nx][ny] == 'X':
                        new_swans.append((nx,ny))
                    swan_chk[nx][ny] = False
 
    if not swan_chk[end_swan[0]][end_swan[1]]:
        answer = times
        break
    waters = new_water
    swans = new_swans
    new_swans = deque()
    new_water = deque()
    times += 1
 
print(answer)

마지막 방식은 deque를 4개를 써서, 매번 bfs를 처음부터 하지 않아도, 되는 방식으로 해주었다.

 

water : 현재가 물인 상태인 것들이 모아져있는 deque

new_water : 다음 시간에 녹아질 예정인 빙하들의 deque

swan : 현재 시간에 swan이 돌아다닐수 있는 deque

new_swan : 다음 시간에 swan이 움직일수 있는 deque

 

이렇게 기능적으로 나눈뒤에,

 

먼저 water에서 다음에 녹을 water를 찾아준다. 이때 new_water에 들어가는 것은 호수에 빙하인것과 water_chk 한번도 방문하지 않은 곳이여야 한다.

그리고 여기서 처음 water를 pop할때 lake[x][y]를 . 를 입력해주는 것은 이전 time에 우리가 찾아놓은 new_water가 녹았기 때문에, 이때 값을 변경시켜주는 것이다.

 

이렇게 한뒤에, swan를 bfs를 돌리면서 물인곳은 계속 swan에 추가해서 bfs를 해주고, 만약 빙하인곳은 다음번에 들릴곳이기 때문에 new_swan에 넣어준다.

그리고 빙하와 물 상관없이 swan 방문을 check해준다.

 

이렇게 작업을 한뒤에, 우리가 찾는 반대편 swan에 도착했는지 확인을 해주고, 그때의 시간을 출력해주면 된다.

 

도착하지 않았으면, new_water를 water에 넣어주고, new_swan을 swan에 넣어준뒤 초기화를 시켜준다