[백준] 백조의 호수

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

3197번: 백조의 호수

BFS를 사용하는 문제입니다. 생각보다 python으로 해결하기에 시간제한이 빡빡한 문제인 것 같습니다.

 

문제부터 요약해보면, 

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

다음과 같이 

X : 빙판

. : 물

L : 백조

로 2차원 배열이 구성되어 있는데, 하루마다 물과 닿은 빙판이 녹고, 이 호수에서 두마리의 백조가 서로 만나려면 며칠이 지나야 하는지를 return 하는 문제입니다. 

 

간단한 예시로 살펴보면,

.L
..
XX
XX
XX
XX
XX
XX
..
.L

 다음과 같은 상황에서는 3일

..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

다음과 같은 상황에서는 2일이 걸립니다. 

이제 풀이법을 설명해보겠습니다. 

 

<Solution>

우선 아이디어는 다음과 같습니다. 

1. 각 빙판이 녹으려면 몇일이 필요한지를 구합니다.  2. 가장 오랫동안 유지되는 빙판을 max, 0을 min으로 하고 time에 대해 binary search(이진탐색)을 합니다.  3. 이에 따른 최소 시간을 return합니다.

총 위와 같이 3개의 step을 진행하게 됩니다. 하지만 이 과정중에서 조금이라도 비효율적인 부분들이 있다면 시간초과가 발생하는 것을 확인 할 수 있습니다. 

 

제가 시간초과로 고민하였던 부분들은 크게 두가지입니다. 

1. 최소시간을 return 하여야 하므로 이진탐색을 하지 않고 작은 수부터 차례대로 검사를 하면 시간초과가 발생합니다.

2. 빙판이 녹는 시간을 구할 때 "X"인 지점들에 대해 BFS를 하였는데 이렇게 하면 시간초과가 발생합니다. 

 

1번 문제의 해결방법은 min과 max값에 대해 binary search를 진행하면 됩니다. 2번 문제의 해결방법은 녹아있는 부분에서 출발하는 bfs를 진행하면 됩니다.

 

실제 구현은 아래와 같습니다. 2번 문제에 대해 올바른 코드와 잘못된 코드 둘다 첨부합니다. 

 

<올바른 코드>

import sys
from collections import deque
move_r = [-1, 1, 0, 0] #up down left right
move_c = [0, 0, -1, 1]
r,c = map(int,sys.stdin.readline().split())
# print(f'r : {r}\nc: {c}')
array = []
time = [[0]*c for _ in range(r)]

def oob(r,c,max_r,max_c):
    return not (r<max_r and r>=0 and c<max_c and c>= 0)

def bfs(array, max_r, max_c, q):
    while q:
        t = q.popleft()
        for i in range(4):
            new_r = t[0]+move_r[i]
            new_c = t[1]+move_c[i]
            if not oob(new_r, new_c, max_r, max_c) and array[new_r][new_c] == 'X' and not visited[new_r][new_c]:
                q.append([new_r,new_c,t[2]+1])
                time[new_r][new_c] = t[2]+1
                visited[new_r][new_c] = 1
                continue
            else:
                continue
    return t[2]

def bfs_binary(min_time, max_time):
    answer = 0
    while min_time <= max_time:
        mid_time = (max_time + min_time)//2
        q = deque([[swan[0][0], swan[0][1]]])
        visited = [[0]*c for _ in range(r)]
        visited[swan[0][0]][swan[0][1]] = 1
        flag = 0
        while q:
            t = q.popleft()
            for j in range(4):
                new_r = t[0]+move_r[j]
                new_c = t[1]+move_c[j]
                if swan[1][0] == new_r and swan[1][1] == new_c:
                    flag = 1
                    break
                if not oob(new_r, new_c, r, c) and time[new_r][new_c] <= mid_time and not visited[new_r][new_c]:
                    q.append([new_r,new_c])
                    visited[new_r][new_c] = 1
            if flag == 1:
                break
        if flag == 1:
            answer = mid_time
            max_time = mid_time-1
        else:
            min_time = mid_time+1
    return answer
    
# build 2D array
for i in range(r):
    #array.append(sys.stdin.readline().strip())
    array.append(list(sys.stdin.readline().strip()))

swan = []

# find time for melting(bfs)
q = deque()
visited = [[0]*c for _ in range(r)]
for i in range(r):
    for j in range(c):
        if array[i][j] == 'L' or array[i][j] == '.':
            if array[i][j] == 'L':
                swan.append([i,j])
            q.append([i,j,0])
            visited[i][j] = 1

min_time = 0
max_time = bfs(array, r, c, q)


# print(f'max_time : {max_time}')
# search min_time (bfs, binary search)

print(bfs_binary(min_time,max_time))

<잘못된 코드>

import sys
from collections import deque
move_r = [-1, 1, 0, 0] #up down left right
move_c = [0, 0, -1, 1]
r,c = map(int,sys.stdin.readline().split())
# print(f'r : {r}\nc: {c}')
array = []
time = [[0]*c for _ in range(r)]

def oob(r,c,max_r,max_c):
    return not (r<max_r and r>=0 and c<max_c and c>= 0)

def bfs(array, r, c, max_r, max_c):
    q = deque()
    q.append([r,c,1])
    visited = [[0]*max_c for _ in range(max_r)]
    visited[r][c] = 1
    while q:
        t = q.popleft()
        for i in range(4):
            new_r = t[0]+move_r[i]
            new_c = t[1]+move_c[i]
            if not oob(new_r, new_c, max_r, max_c) and array[new_r][new_c] == 'X' and not visited[new_r][new_c]:
                q.append([new_r,new_c,t[2]+1])
                visited[new_r][new_c] = 1
                continue
            elif not oob(new_r, new_c, max_r, max_c) and (array[new_r][new_c] == '.' or array[new_r][new_c] == 'L'):
                return t[2]
            else:
                continue

def bfs_binary(min_time, max_time):
    answer = 0
    while min_time <= max_time:
        mid_time = (max_time + min_time)//2
        q = deque([[swan[0][0], swan[0][1]]])
        visited = [[0]*c for _ in range(r)]
        visited[swan[0][0]][swan[0][1]] = 1
        flag = 0
        while q:
            t = q.popleft()
            for j in range(4):
                new_r = t[0]+move_r[j]
                new_c = t[1]+move_c[j]
                if swan[1][0] == new_r and swan[1][1] == new_c:
                    flag = 1
                    break
                if not oob(new_r, new_c, r, c) and time[new_r][new_c] <= mid_time and not visited[new_r][new_c]:
                    q.append([new_r,new_c])
                    visited[new_r][new_c] = 1
            if flag == 1:
                break
        if flag == 1:
            answer = mid_time
            max_time = mid_time-1
        else:
            min_time = mid_time+1
    return answer
    
# build 2D array
for i in range(r):
    #array.append(sys.stdin.readline().strip())
    array.append(list(sys.stdin.readline().strip()))

swan = []

# find time for melting(bfs)
min_time = 0
max_time = 0
for i in range(r):
    for j in range(c):
        if array[i][j] == 'X':
            time[i][j] = bfs(array,i,j,r,c)
            if time[i][j] > max_time:
                max_time = time[i][j]
        if array[i][j] == 'L':
            swan.append([i,j])

# print(f'max_time : {max_time}')
# search min_time (bfs, binary search)

print(bfs_binary(min_time,max_time))