[BFS] 일자 기준에 따른 counting

아래 유형들은 최소 일자를 count하는 것이기 때문에 BFS를 수행할 때, 방문한 노드를 queue에 넣기 이전에 동일한 날짜에 시작하는 point부터 먼저 queue로 넣어야 한다.

 

추가로 현재 위치하는 counting이 같은 날짜이므로 이후 누적되는 날짜를 더해주어야하기 때문에 visited에 들어간 값에 +1을 해주며 날짜를 누적하는 방식으로 동작함을 기억하자.

대표 예재, 백준의 토마토

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

7576번: 토마토

 

이 문제는 일반적인 2D를 사용. 전에 풀었던 파트

m, n = [int(x) for x in input().split()]

maps = [[int(x) for x in input().split()] for _ in range(n) ]

from collections import deque

queue = deque()

############### 이 문제에서 알아야 할 아이디어 (1)
########## 탐색한 노드의 다음 이웃 노드들이 아니라, 먼저 감염이 된 같은 날의 토마토를 기준으로 BFS를 수행해야 함
########## 따라서 queue에 주변 노드가 아니라, 감염된 노드부터 먼저 봐주어야 하기 때문에 먼저 감염된 토마토를 아래 for loop를 통해 queue에 집어넣음
for i in range(n) :
    for j in range(m) :
        if maps[i][j] == 1 :
            queue.append([i,j])

move_x = [-1,1,0,0]
move_y = [0,0,1,-1]


### 언제를 하루 기준으로 잡아야할까?
while queue :
    x, y = queue.popleft()

    for k in range(4) :
        after_x = x+move_x[k]
        after_y = y+move_y[k]

        if after_x < 0 or after_y < 0 or after_x >= n or after_y >= m :
            continue

        if maps[after_x][after_y] == 0 :
            queue.append([after_x,after_y])
            #################### 이 문제에서 알아야 할 아이디어 (2)
            ######## 누적되는 값을 통해 일자를 tracking 할 수 있음
            maps[after_x][after_y] = maps[x][y] + 1
            
flag = False
answer = 0

### 여기 마이너하지만 조건 체크 조심하자
for row in maps :
    if 0 in row :
        flag = True
        break
    answer = max(answer,max(row))

if flag :
    print(-1)
else :
    print(answer)

 

 

이 문제는 3D를 사용하는 점에서 일반적인 2D와는 다른 문제

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

7569번: 토마토

from collections import deque
M, N, H = [int(x) for x in input().split()]

maps = []
for _ in range(H) :
    floor = []
    for _ in range(N) :
        floor.append([int(x) for x in input().split()])
    maps.append(floor)

### 3차원에서 움직임을 기억 
move_x = [0,0,-1,1,0,0]
move_y = [0,0,0,0,-1,1]
move_h = [-1,1,0,0,0,0]

visited = []
for _ in range(H) :
    floor_visited = [ [0]*M for _ in range(N) ]
    visited.append(floor_visited)

queue = deque()

def BFS(queue) :
    while queue :
        h,x,y = queue.popleft()

        for k in range(6) :
            after_h = h+move_h[k]
            after_x = x+move_x[k]
            after_y = y+move_y[k]

            if after_h < 0 or after_x < 0 or after_y < 0 or after_h >= H or after_x >= N or after_y >= M :
                continue

            if visited[after_h][after_x][after_y] == 0 and maps[after_h][after_x][after_y] == 0 :
                visited[after_h][after_x][after_y] = visited[h][x][y] + 1
                queue.append([after_h,after_x,after_y])

########### 중요!! 토마토 유형처럼 최저 일자를 구하는 문제 유형은 먼저 익은 토마토부터 queue에 모조리 넣어주고 시작 ##############
for h in range(H) :
    for i in range(N) :
        for j in range(M) :
            if maps[h][i][j] == 1 :
                visited[h][i][j] = 1
                queue.append([h,i,j])

BFS(queue)

######### 방문 기록도 없으며 익지 않은 토마토가 존재하는 경우에 -1 반환
for h in range(H) :
    for x in range(N) :
        for y in range(M) :
            if visited[h][x][y] == 0 and maps[h][x][y] == 0 :
                print(-1)
                exit(0)

curr_max = 0
for h in range(H) :
    for x in range(N) :
        now = max(visited[h][x])
        if now > curr_max:
            curr_max = now

print(curr_max-1)