[BOJ/Python] 3197. 백조의 호수 (Platinum 5)

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

 

 

접근

# 1. 시간초과 (매번 처음부터 BFS 시작) 

 

매일 물 공간과 상하좌우로 접촉한 모든 빙판 공간은 녹는다. 

두 백조가 만나려면 며칠이 걸릴까?  

 

1. 먼저 두 백조의 위치를 찾는다. (L1, L2)

2. 두 백조가 만날 수 있을 때까지 아래를 반복한다.

    2-1. L1 위치에서 bfs를 시작하여 L2 위치까지 갔다면 종료한다.

    2-2. 빙판에 막혔다면 물 공간과 접한 빙판 공간을 모두 녹이고 걸리는 날을 카운트한다. 

 

전체 코드

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

R, C = map(int, input().split())
lake = []
swan = []

dx = (0,0,1,-1)
dy = (1,-1,0,0)

# 입력받은 호수에서 두 백조의 위치 (L1, L2) 찾기
for i in range(R):
    temp = input().strip()
    for j in range(C):
        if temp[j] == 'L':
            swan.append((i,j))
    lake.append(list(temp))


# L1에서 L2까지 탐색
def bfs(x, y):
    q = deque()
    visited = [[0]*C for _ in range(R)]
    q.append((x, y))
    visited[x][y] = 1
    
    while q:
        x, y = q.popleft()
        if x == swan[1][0] and y == swan[1][1]:
            return True
        
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if lake[nx][ny] != 'X' and visited[nx][ny] == 0:
                    q.append((nx,ny))
                    visited[nx][ny] = 1
    return False

# 빙판 공간을 녹이는 함수
def melt():
    melting_points = []
    for i in range(R):
        for j in range(C):
            if lake[i][j] == '.':
                for k in range(4):
                    nx, ny = i+dx[k], j+dy[k]
                    if 0 <= nx < R and 0 <= ny < C:
                        if lake[nx][ny] == 'X':
                            melting_points.append((nx,ny))
    for x,y in melting_points:
        lake[x][y] = '.'                      
    

answer = 0
while True:
    if bfs(swan[0][0],swan[0][1]): # L1에서 L2까지 이동했다면 
        print(answer) # 걸리는 날 출력 
        break
    else: # # L1에서 L2까지 이동하지 못했다면 
        answer += 1  # 걸리는 날 +1
        melt()  # 빙판 녹임

 

그러나 ?

시간 초과 발생

플래티넘이라 겁먹었는데 어쩐지 스무스하다싶었다. 

 

어디 부분에서 시간초과를 줄일 수 있을까 생각해보았다.

우선 bfs를 매번 L1위치부터 시작하는 것도 쓸데없이 똑같은 연산을 계속하는 걸지도? 

왜냐하면 L1부터 쭉 가다가 중간에 빙판에 막혀서, 그 빙판을 녹인 후 다시 L1부터 이동하기 때문이다. 

 

그렇다면 중간에 막혔던 부분부터 다시 시작한다면?

그럼 그 막혔던 빙판 위치를 저장해두고, 빙판을 녹인 후 다시 그 위치부터 시작하면 될까?

 

# 2. 시간초과 ( 빙판에 막히기 전 물 공간부터 bfs 시작 )

막혔던 빙판 위치 대신 빙판에 막히기 직전 물 공간 위치부터 다시 bfs를 시작하도록 바꿔서 제출해보았다.  

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

R, C = map(int, input().split())
lake = []
swan = []

dx = (0,0,1,-1)
dy = (1,-1,0,0)

for i in range(R):
    temp = input().strip()
    for j in range(C):
        if temp[j] == 'L':
            swan.append((i,j))
    lake.append(list(temp))


def bfs(x, y):
    q = deque()
    visited = [[0]*C for _ in range(R)]
    q.append((x, y))
    visited[x][y] = 1
    

    while q:
        x, y = q.popleft()
        if x == swan[1][0] and y == swan[1][1]:
            return True, () 
        
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if lake[nx][ny] != 'X' and visited[nx][ny] == 0:
                    q.append((nx,ny))
                    visited[nx][ny] = 1
    return False, (x, y) # 빙판에 막히기 직전 물 공간 위치 반환 

def melt():
    melting_points = []
    for i in range(R):
        for j in range(C):
            if lake[i][j] == '.':
                for k in range(4):
                    nx, ny = i+dx[k], j+dy[k]
                    if 0 <= nx < R and 0 <= ny < C:
                        if lake[nx][ny] == 'X':
                            melting_points.append((nx,ny))
    for x,y in melting_points:
        lake[x][y] = '.'                      
    

answer = 0
stop_x, stop_y = swan[0][0],swan[0][1] 
while True:
    succ, stop_pos = bfs(stop_x, stop_y) # 빙판에 막히기 직전 위치부터 시작 
    if succ:
        print(answer)
        break
    else:
        stop_x, stop_y = stop_pos 
        answer += 1
        melt()

 

2%까지 올라가다가 시간초과..! 이전보단 나아지긴 했나보다. 

뭔가 아예 다르게 생각해야할 것 같았고 결국 질문을 눌러 확인을 하였다. 

https://www.acmicpc.net/board/view/65437

 

 

시간 초과의 포인트는

프로그램 전체에서 얼음을 녹이는 BFS와 백조가 만나는지 확인하는 BFS가 각각 한번만 진행되어야한다.

통틀어 한번이라는 소리는 한번 체크했던 곳은 다시 가지 않아야 한다는 것이다. 

 

https://itsmain.tistory.com/10

위의 블로그를 통해 이해하였고 그대로 짜보았다.

백조가 만나는지 체크하고 물을 녹이는 것을 한 주기라고 한다. 다음 주기 때 좌표를 저장하여 이전 주기 때 체크했던 것들을 다시 ㅔ크하는 상황을 피할 수 있다. 

 

swan_queue : 백조가 다른 백조를 찾을 때 물 '.'을 만날 경우 계속 이동하기 위한 큐 next_queue: 백조가 빙판 'X'를 만나면 나중에 물을 녹인 후 확인하기 위한 큐 water : 물의 좌표를 담는 큐next_water : 빙판을 녹여서 물로 만든 좌표를 담음 (다음 주기 때 다시 상하좌우에  'X'가 있는 체크하기 위해)

 

swan_queue에는 next_queue로 복사되고

water는 next_water로 복사되어 사용된다. 

 

코드로 보자면

R, C = map(int, input().split())
lake = []
swan = []
water = deque()

# 데이터 입력 
for i in range(R):
    temp = input().strip()
    for j in range(C):
        if temp[j] == '.' or temp[j] == 'L': # 물 or 백조일 경우
            water.append((i,j))
        if temp[j] == 'L':
            swan.append((i,j))
    lake.append(list(temp))
    
answer = 0
visited = [[0]*C for _ in range(R)]
swan_queue = deque()

x, y = swan[0][0],swan[0][1] 
swan_queue.append((x,y))
visited[x][y] = 1

while True:
    found, next_queue = bfs()
    if found:
        break
    answer += 1
    water = melt()
    swan_queue = next_queue
        

print(answer)

 

전체적인 흐름

• lake에 호수의 정보, swan에는 백조의 위치, water는 물 또는 백조인 위치를 담는다. water는 빙판이 아닌 곳, 백조가 움직일 수 있는 공간이라고 볼 수 있다. 
• visited는 전체적으로 중복 체크를 방지하기 위해 사용된다.
• 두 백조 중 한 백조를 swan_queue에 넣고 해당 백조의 위치를 방문처리한다. 
• 또 다른 백조를 만나기 위한 탐색 bfs()를 돌린다. 
  • 만약 만났다면 break
  • 아니라면 걸리는 날 수 answer를 증가시켜주고 melt()를 통해 빙판을 녹인다.
  • water에는 이번에 녹은 물의 좌표가 있고, 다음 주기에  해당 좌표의 상하좌우를 체크하여 빙판을 녹일 수 있다.
  • swan_queue는 next_queue로 복사되는데, next_queue는 이번 주기에 녹인 빙판의 좌표들이다. 물이 되었기 때문에 백조가 탐색할 부분들이 되는 것이다. 

 

def bfs():
    next_queue = deque() 
    while swan_queue:
        x, y = swan_queue.popleft()
        if x == swan[1][0] and y == swan[1][1]:
            return True, None
        
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if visited[nx][ny]: continue 
                if lake[nx][ny] != 'X': # 물이라면 계속 이동을 위해 큐에 삽입
                    swan_queue.append((nx,ny))
                else: # 빙판이라면 나중에 물을 녹인 후 확인할 큐에 삽입 
                    next_queue.append((nx,ny))
                visited[nx][ny] = 1
                    
    return False, next_queue

• bfs로 두 백조가 만나는지 확인하는 함수이다.
• 상하좌우를 탐색하면서
  • 해당 위치가 빙판이 아니라면 계속 이동하기 위해 swan_queue에 좌표를 삽입하고
  • 해당 위치가 빙판이라면 이번 주기에 물이 되기 때문에 다음 주기에 확인하기 위해 next_queue에 좌표를 삽입한다.
  • 해당 위치에 대한 체크는 끝났기에 방문처리한다.
• swan_queue에서 pop한 좌표가 찾고 있는 백조라면 True 반환
• 결국 만나지 못했다면 False와 next_queue를 반환 

 

def melt():
    next_water = deque()
    while water:
        x, y = water.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if lake[nx][ny] == 'X':
                    next_water.append((nx,ny))
                    lake[nx][ny] = '.'
            
    return next_water

• 빙판을 물로 녹이는 melt 함수이다.
•  현재 물인 공간을 상하좌우 탐색하면서 빙판을 만난다면 next_water에 좌표를 삽입한다. 다음 주기에 해당 좌표들의 상하좌우를 탐색해야하기 때문이다.
• 그리고 빙판을 물로 녹인 것을 lake에 갱신한다. 

 

최종 코드 

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

dx = (0,0,1,-1)
dy = (1,-1,0,0)

# 두 백조가 만나는지 확인하는 함수 
def bfs():
    next_queue = deque() 
    while swan_queue:
        x, y = swan_queue.popleft()
        if x == swan[1][0] and y == swan[1][1]:
            return True, None
        
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if visited[nx][ny]: continue 
                if lake[nx][ny] != 'X': # 물이라면 계속 이동을 위해 큐에 삽입
                    swan_queue.append((nx,ny))
                else: # 빙판이라면 나중에 물을 녹인 후 확인할 큐에 삽입 
                    next_queue.append((nx,ny))
                visited[nx][ny] = 1
                    
    return False, next_queue

# 빙판을 물로 녹이는 함수 
def melt():
    next_water = deque()
    while water:
        x, y = water.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if lake[nx][ny] == 'X':
                    next_water.append((nx,ny))
                    lake[nx][ny] = '.'
            
    return next_water                
    
R, C = map(int, input().split())
lake = []
swan = []
water = deque()

# 데이터 입력 
for i in range(R):
    temp = input().strip()
    for j in range(C):
        if temp[j] == '.' or temp[j] == 'L':
            water.append((i,j))
        if temp[j] == 'L':
            swan.append((i,j))
    lake.append(list(temp))


answer = 0
visited = [[0]*C for _ in range(R)]
swan_queue = deque()

x, y = swan[0][0],swan[0][1]
swan_queue.append((x,y))
visited[x][y] = 1

while True:
    found, next_queue = bfs()
    if found:
        break
    answer += 1
    water = melt()
    swan_queue = next_queue
        

print(answer)

 

느낀점

첫 플레티넘 문제였는데 역시나 어려운 문제였다. 이런 방식으로 사고해본 적이 거의 없는 것 같다.

BFS 문제의 여러 유형을 풀어봤다고 생각했는데 아직 멀었나보다. 

어쨌든 중요한 것은 중복 체크를 하지 않게 정보를 저장하는 것, 다음 주기에 해야할 부분만 정해놓고 돌리는 것이었다.

이해하려고 코드 하나 하나를 뜯어보면서 이렇게도 풀 수 있구나 싶었고 나름 재밌기도 한 정리였다!