백준 7576번 BFS

서론

7576번: 토마토

여전히 단계별로 문제를 푸는 중입니다. 지금은 BFS, DFS 단계인데 BFS, DFS가 알고리즘이긴 하지만 보통의 문제들은 이것을 사용해서 구현하는 문제이기 때문에 모르면 전혀 풀 수 없는 순수한 알고리즘 문제들보다는 훨씬 재밌었습니다. BFS, DFS는 그렇게 어려운 편은 아니고 시간을 들여서 풀면 다 풀 수 있는 문제들인데 이번에는 좀 새로운 유형이 나와서 기록합니다.

토마토가 익을 때 한 번의 탐색에서 탐색 된 노드들은 한 번(하루)으로 취급해야 하는 것이 핵심인데 저는 여기서 한 번의 탐색 후에 큐 자체에 구분자를 넣어서 해결했습니다.

제한 조건

BFS, DFS 문제들은 제한을 심하게 두진 않기 크게 신경 쓰지 않아도 되지만 그래도 최적화를 위해서 탐색해야 하는 graph나 map은 한 번만 훑는 것이 좋고 또 함수를 사용한다면 함수 내에 인자로 전달해서 괜히 복사하여 시간과 메모리를 잡아먹지 말고 그냥 전역변수로 사용하는 것이 좋습니다.

• 시간제한 - 1초

시간제한은 1초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. map의 최대크기가 1,000*1,000 = 백만이기 때문에 map을 한 번만 훑으면 문제가 되지 않습니다. map을 훑으면서 BFS 함수를 호출하더라도 큰 문제는 없을 것 같습니다. 위에서 말한 것만 지켜주면 시간제한은 크게 신경 쓰지 않아도 될 것 같습니다.

• 메모리 제한 - 256MB

메모리 제한은 256MB입니다. 데이터의 개수는 백만 개기 때문에 int 형 데이터라고 생각한다면 4MB입니다. 역시 위에서 말했던 것처럼 괜히 함수에서 복사하여 메모리 잡아먹지 말고 전역변수로 사용한다면 크게 신경 쓰지 않아도 될 것 같습니다.

BFS

일반적인 BFS 문제입니다. 토마토가 하루에 한 번씩 근접한 곳을 익게 만들어야 하니 DFS는 안되고 BFS를 사용해야 합니다. 익은 토마토를 기준으로 주변을 탐색하여 큐에 넣고 거기서부터 조건에 따라 익은 토마토를 전파하면 되는 문제입니다.

특이점으로는 탐색 한번이 문제의 행동에서의 한 번(하루)이 되는 것이 아니라 한 번의 탐색에서 큐에 넣은 노드들을 세트로 한 번(하루)으로 봐야 되기 때문에 이 부분을 해결해야 합니다. 고민하다가 탐색한 노드들을 큐에 넣고 구분자를 넣어서 세트를 끊어주기로 했습니다. 코드가 그렇게 이쁜 것 같진 않아서 다른 사람들 코드도 찾아봤는데 대부분 비슷하게 했습니다.

저 같은 경우는 큐에 bfs.append([-1,-1])을 사용하여 구분자를 넣었는데 제 코드에서 큐에 넣는 데이터 형식이 map의 [y, x]였기 때문에 구분자로 y, x로 나올 수 없는 값을 넣었습니다. 제어 할 수만 있다면 무슨 값을 넣어도 무방합니다. 전체 코드는 아래와 같습니다.

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

m,n = map(int,input().split())
map = [list(map(int,input().split())) for __ in range(n)]

def bfs(start_list):
    bfs = dq()
    ## 탐색을 시작해야 하는 출발지가 여러 개기 때문에 여러 개 넣습니다.
    for starty,startx in start_list:
        bfs.append([starty, startx])
    ## 구분자
    bfs.append([-1,-1])
    cnt = 0
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    while bfs:
        basey, basex = bfs.popleft()
        ## 구분자가 나올 경우 하루가 지났다고 판단합니다.
        if basey == -1 and bfs:
            cnt += 1
            bfs.append([-1,-1])
        else:
            for i in range(4):
                y = basey+dy[i]
                x = basex+dx[i]
                if (y >= 0 and y < n) and (x >= 0 and x < m) and map[y][x] == 0:
                    map[y][x] = 1
                    bfs.append([y, x])
    ## 모든 행동을 끝냈는데 map에 아직 0이 남아있다면 토마토를 다 익힐 수없는 경우입니다.
    for row in map:
        if 0 in row:
            return -1
    return cnt

start_list = []
for i in range(n):
    for j in range(m):
        if map[i][j] == 1:
            start_list.append([i,j])

print(bfs(start_list))

생각

그래도 풀면서 나름 신선했던 문제 같아서 기록해봤는데 또 그 정도 문제는 아닌 것 같습니다. BFS, DFS 문제를 빨리 쭉쭉 풀어봐야겠습니다.

*추가

같은 카테고리의 다른 문제들을 풀다 보면 더 좋은 코드가 생각나는데 이번에도 구분자를 넣는 새로운 방법이 생각나서 적습니다. 사실 큐 안에 구분자를 넣는다는 건 큐의 데이터 형식을 훼손하는 개념이었습니다. 제어할 수 있는 값이라고 해도 처음부터 [y, x]라는 좌표 데이터를 넣는다고 설계했는데 [-1,-1]을 넣게 되면서 코드가 조금 이상해지지 않았나 생각을 했습니다.

그래서 생각한 게 처음부터 [y, x]를 큐에 넣는 게 아니라 [y, x, day]를 큐에 넣는 방법입니다. 이렇게 하면 따로 구분자를 걸러내야 하는 조건 없이도 그냥 그 자체로 day 값을 가지게 됩니다. 적어 놓고 보니 BFS에서 최단 거리를 찾는 개념과 비슷합니다. 사소한 부분이고 성능에도 크게 영향을 미칠 것 같진 않지만, 코드가 더 이쁜 것 같습니다. 전체 코드는 아래와 같습니다.

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

m,n = map(int,input().split())
map = [list(map(int,input().split())) for __ in range(n)]

def bfs(start_list):
    bfs = dq()
    ## 탐색을 시작해야 하는 출발지가 여러 개기 때문에 여러 개 넣습니다.
    ## 구분자를 삭제했습니다.
    for starty,startx in start_list:
        bfs.append([starty, startx, 0])
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]

    while bfs:
        basey, basex, day = bfs.popleft()
        for i in range(4):
            y = basey+dy[i]
            x = basex+dx[i]
            if (y >= 0 and y < n) and (x >= 0 and x < m) and map[y][x] == 0:
                map[y][x] = 1
                ## 이런식으로 day값을 컨트롤합니다.
                bfs.append([y, x, day+1])
    ## 모든 행동을 끝냈는데 map에 아직 0이 남아있다면 토마토를 다 익힐 수없는 경우입니다.
    for row in map:
        if 0 in row:
            return -1
    return day

start_list = []
for i in range(n):
    for j in range(m):
        if map[i][j] == 1:
            start_list.append([i,j])

print(bfs(start_list))