[BFS] BOJ_3197 백조의 호수

문제

백준 백조의 호수

맞은 사람이 1440명이라는 골드1 전설의 문제, 백조의 호수에 도전했다.

python3로는 통과가 안되고 통과 조건도 매우 까다로워서 전역변수를 지역변수로 바꾸고 여러 방법을 시도한 끝에 9시간만에 통과할 수 있었다.

첫번째 접근

0일부터 백조가 이동 가능할때까지 얼음 녹이고(bfs) 백조 이동가능성 판단(bfs)하는걸 반복하자

그냥 생각 없이 부르트 포스 방식으로 풀고 봤다.

1. move_swan() , melt_ice() 구현
2. while 문 돌리면서 move_swan()의 결과가 True일때 count 값 return
3. move_swan()의 결과가 False일때
   1. count += 1
   2. melt_ice() :인접한 얼음들 녹이기

전체 코드

import collections

R, C = map(int,input().split(" "))

map = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]

swans = []
ices = []

# 입력
for i in range(R):
    line = input()

    for j in range(C):
        if line[j] == 'L':
            swans.append((i, j))

        if line[j] == '.':
            ices.append((i,j))
    map.append(list(line))


def melt_ice():
    new_ices = []
    global ices

    for ice in ices:
        y, x = ice
        for i in range(4):
            t_y, t_x = y + dy[i], x + dx[i]

            if t_y < R and t_x < C and t_y >= 0 and t_x >= 0:
                if map[t_y][t_x] == 'X':
                    map[t_y][t_x] = '.'
                    new_ices.append((t_y,t_x))

    ices = new_ices

def move_swan():
    y1, x1 = swans[0]
    y2, x2 = swans[1]

    queue = collections.deque()

    visited = set()

    for i in range(4):
        queue.append((y1 + dy[i], x1 + dx[i]))

    while queue:
        y, x = queue.popleft()

        if (y,x) in visited:
            continue

        visited.add((y,x))

        if (y, x) == (y2, x2):
            return True

        for i in range(4):
            t_y, t_x = y + dy[i], x + dx[i]

            if t_y < R and t_x < C and t_y >= 0 and t_x >= 0:
                if map[t_y][t_x] != 'X' and (t_y, t_x) not in visited:
                    queue.append((t_y, t_x))

    return False


count = 0

while True:
    if move_swan():
        break

    count += 1
    melt_ice()

print(count)

결과

시간초과

그럴수밖에 없다

while문을 한번 돌때마다 bfs가 두번 돌아가니 시간 복잡도는

O(max(R, C) X 2 X R X C) 가 된다.

두번째 접근

1. 백조가 위치한 L 도 물이다!!

2. 백조 이동 가능성을 계산하기 전에 map을 돌면서 날짜별로 물이 되는 그래프를 미리 만들어 놓는다

   1. R * C 크기를 가지고 0으로 초기화된 2차원 배열인 times를 만들고 물이 되는 시간을 측정한 값을 저장했다.
   2. 이 과정에서 가장 값이 큰 날짜를 max_day로 정한다.

3. 백조 1과 백조2가 만나는 날은 0에서 max_day 사이일 것이다.

4. 3번을 계산할때 Binary Search를 이용하자!!!!

Binary Search와 BFS

사진 속 초록색 글씨 부분은 입력값이고 그 아래 검은색 글씨 부분은 얼음이 녹기까지 걸리는 시간을 계산한 배열 times를 출력한 값이다.
노란색 박스는 백조의 위치와 같다.

왼쪽 상단 박스를 백조1, 오른쪽 하단 박스를 백조2라고 지칭하도록 하자

melt_ice()에서 구한 max_day가 3이었기 때문에 백조 1에서 백조2는 3일 안에는 무조건 만난다.

그렇다면 move_swan()으로 백조를 움직일 때 binary search를 통해 최적의 시간을 구할 수 있다.

만약 max_day가 8이고 백조1이 백조2를 만나는데 6일이 걸린다고 하면

day = 0
while day <= max_day:
  if move_swan(day):
    break
   day += 1
 
print(day)

위와 같이 구현할 수 있는데 시간복잡도는 눈물이 난다.
move_swan()은 크기 RXC인 인접행렬 times를 bfs() 하는 함수이므로 O(max_day X R X C) 가 된다.

하지만 선형탐색이 아닌 이진탐색을 한다면 어떨까?

0에서 출발해서 6이 될때까지 탐색하는게 아니라 0과 8의 중간값인 4에서 출발해서 범위를 반반씩 나눠 간다면 시간 복잡도는 O(log max_day X R X C)이 된다.

결과

pypy3로 통과

전체 코드

# https://www.acmicpc.net/problem/3197
# 백조의 호수

import collections, sys

R, C = map(int, sys.stdin.readline().split(" "))

lake = []
times = [[0 for _ in range(C)] for _ in range(R)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]

swans = []
visited = [[False for _ in range(C)] for _ in range(R)]
waters = collections.deque()
max_time = 0


# 입력
for i in range(R):
    line = sys.stdin.readline()

    for j in range(C):
        if line[j] == 'L':
            swans.append((i, j))

        if line[j] != 'X':
            waters.append((i, j))
            visited[i][j] = True

    lake.append(list(line[:-1]))


def melt_ice(lake):
    max_time = 0

    while waters:
        y, x = waters.popleft()

        for i in range(4):
            t_y, t_x = y + dy[i], x + dx[i]

            if 0 <= t_y < R and 0 <= t_x < C and visited[t_y][t_x] == False:
                if lake[t_y][t_x] == 'X':
                    times[t_y][t_x] = times[y][x] + 1
                    waters.append((t_y,t_x))
                    visited[t_y][t_x] = True
                    max_time = times[t_y][t_x]

    return max_time

def move_swan(lake, swans, max_num):
    y1, x1 = swans[0]
    y2, x2 = swans[1]


    queue = collections.deque()
    s_visited = [[False for _ in range(C)] for _ in range(R)]

    queue.append((y1, x1))
    s_visited[y1][x1] = True

    while queue:
        y, x = queue.popleft()


        for i in range(4):
            t_y, t_x = y + dy[i], x + dx[i]

            if (t_y, t_x) == (y2, x2):
                return True

            if 0 <= t_y < R and 0 <= t_x < C and s_visited[t_y][t_x] == False:
                if lake[t_y][t_x] == 'L' or lake[t_y][t_x] == '.' or times[t_y][t_x] <= max_num:
                    s_visited[t_y][t_x] = True
                    queue.append((t_y, t_x))

    return False



_min , _max = 0, melt_ice(lake)
answer = _max

while _min <= _max:
    mid = (_min + _max) // 2

    if move_swan(lake, swans, mid):
        _max = mid - 1
        answer = min(answer, mid)

    else:
        _min = mid + 1

print(answer)