<청춘> 격정적으로 사는 것

밤을 새고 공부한 다음 날 새벽에 느꼈던 생생한 환희와 야생적인 즐거움을 잊을 수 없다

코딩테스트/백준

[백준] 7576번 : 토마토 / BFS / 파이썬 Python

수학도 2021. 6. 22. 17:46

토마토 성공출처

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초 256 MB 90429 31387 19608 33.440%

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다.

토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.

철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라.

단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다.

M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다.

둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다.

즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다.

하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다.

정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.

만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1 복사

6 4

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1

예제 출력 1 복사

8

예제 입력 2 복사

6 4

0 -1 0 0 0 0

-1 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1

예제 출력 2 복사

-1

예제 입력 3 복사

6 4

1 -1 0 0 0 0

0 -1 0 0 0 0

0 0 0 0 -1 0

0 0 0 0 -1 1

예제 출력 3 복사

6

예제 입력 4 복사

5 5

-1 1 0 0 0

0 -1 -1 -1 0

0 -1 -1 -1 0

0 -1 -1 -1 0

0 0 0 0 0

예제 출력 4 복사

14

예제 입력 5 복사

2 2

1 -1

-1 1

예제 출력 5 복사

0

 

 

정답 코드

from collections import deque

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

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

def bfs(queue):
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx, ny))
                    

# 익은 토마토 노드와 인접한 아직 익지 않은 토마토 노드가 있다면 방문
queue = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i, j))

bfs(queue)

max = 0
for i in range(n):
    if max == -1:
        break
    for j in range(m):
        if graph[i][j] == 0:
            max = -1
            break
        if graph[i][j] > max:
            max = graph[i][j] - 1 # 익은 날짜를 1부터 시작했으니까 다시 빼줌
print(max)

 

이해를 돕기 위해 출력문을 추가한 코드

from collections import deque

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

for i in range(n):
    print(graph[i])

# 이동할 네 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 주의 : bfs의 매개변수가 queue이다. (이유는 아래에서 설명)
def bfs(queue):
    # 큐가 빌때까지 반복
    while queue:
        x, y = queue.popleft()
        print('x, y = ', x, y)
        # 현재 위치에서 네 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 토마토 창고 범위 안에 있는 경우만 확인
            if 0 <= nx < n and 0 <= ny < m:
                # 익지 않은 토마토가 있다면
                if graph[nx][ny] == 0:
                    # 방문처리 (이전 노드 값 + 1) → 노드 값이 1인 곳 상하좌우는 2가 되고, 2인 곳 상하좌우는 3이 되고 ..
                    graph[nx][ny] = graph[x][y] + 1
                    # 방문한 곳의 상하좌우도 확인하기 위해 큐에 방문좌표 추가
                    queue.append((nx, ny))
                    for i in range(n):
                        print(graph[i])
                    

# 익은 토마토가 있는 좌표들을 미리 queue에 다 넣어주는 과정
queue = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i, j))

# bfs 수행
bfs(queue)

# 토마토가 모두 익을 때까지의 최소 날짜 출력 과정
max = 0  # 최소 날짜 변수
for i in range(n):
	# 위의 for 문 탈출 (i 에 해당하는 for문)
    if max == -1:
        break
    for j in range(m):
        # bfs 수행 후 graph 에 익지 않은 토마토(0)가 존재한다면 max 에 -1 을 넣어주고 위의 for문 탈출 (j에 해당하는 for문)
        if graph[i][j] == 0:
            max = -1
            break
        # 더 큰 날짜로 갱신
        if graph[i][j] > max:
            max = graph[i][j] - 1 # 익은 날짜를 1부터 시작했으니까 다시 빼줌
print(max)


# 예제 입력 1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

# graph
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]

# bfs 수행
x, y =  3 5
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 0, 1]

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 2, 1]

x, y =  2 5
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 2, 1]

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 0, 2, 1]

x, y =  3 4
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 3, 2, 1]

x, y =  1 5
[0, 0, 0, 0, 0, 4]
[0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 3, 2, 1]

[0, 0, 0, 0, 0, 4]
[0, 0, 0, 0, 4, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 3, 2, 1]

x, y =  2 4
[0, 0, 0, 0, 0, 4]
[0, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 0, 3, 2, 1]

x, y =  3 3
[0, 0, 0, 0, 0, 4]
[0, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]

x, y =  0 5
[0, 0, 0, 0, 5, 4]
[0, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]

x, y =  1 4
[0, 0, 0, 0, 5, 4]
[0, 0, 0, 5, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]

x, y =  2 3
[0, 0, 0, 0, 5, 4]
[0, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 0, 4, 3, 2, 1]

x, y =  3 2
[0, 0, 0, 0, 5, 4]
[0, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]

x, y =  0 4
[0, 0, 0, 6, 5, 4]
[0, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]

x, y =  1 3
[0, 0, 0, 6, 5, 4]
[0, 0, 6, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]

x, y =  2 2
[0, 0, 0, 6, 5, 4]
[0, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]

x, y =  3 1
[0, 0, 0, 6, 5, 4]
[0, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  0 3
[0, 0, 7, 6, 5, 4]
[0, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  1 2
[0, 0, 7, 6, 5, 4]
[0, 7, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  2 1
[0, 0, 7, 6, 5, 4]
[0, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  3 0

x, y =  0 2
[0, 8, 7, 6, 5, 4]
[0, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  1 1
[0, 8, 7, 6, 5, 4]
[8, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  2 0

x, y =  0 1
[9, 8, 7, 6, 5, 4]
[8, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  1 0

x, y =  0 0

# bfs 수행 후 graph에서 가장큰값 - 1 하면 토마토가 모두 익을 때까지의 최소 날짜이다.
8

 

# 예제 2번

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

#graph
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]

# bfs 수행
x, y =  3 5
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 0, 1]

[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 2, 1]

x, y =  2 5
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 2, 1]

[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 0, 2, 1]

x, y =  3 4
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 3, 2, 1]

x, y =  1 5
[0, -1, 0, 0, 0, 4]
[-1, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 3, 2, 1]

[0, -1, 0, 0, 0, 4]
[-1, 0, 0, 0, 4, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 3, 2, 1]

x, y =  2 4
[0, -1, 0, 0, 0, 4]
[-1, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 0, 3, 2, 1]

x, y =  3 3
[0, -1, 0, 0, 0, 4]
[-1, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]

x, y =  0 5
[0, -1, 0, 0, 5, 4]
[-1, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]

x, y =  1 4
[0, -1, 0, 0, 5, 4]
[-1, 0, 0, 5, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]

x, y =  2 3
[0, -1, 0, 0, 5, 4]
[-1, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 0, 4, 3, 2, 1]

x, y =  3 2
[0, -1, 0, 0, 5, 4]
[-1, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]

x, y =  0 4
[0, -1, 0, 6, 5, 4]
[-1, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]

x, y =  1 3
[0, -1, 0, 6, 5, 4]
[-1, 0, 6, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]

x, y =  2 2
[0, -1, 0, 6, 5, 4]
[-1, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]

x, y =  3 1
[0, -1, 0, 6, 5, 4]
[-1, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  0 3
[0, -1, 7, 6, 5, 4]
[-1, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  1 2
[0, -1, 7, 6, 5, 4]
[-1, 7, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  2 1
[0, -1, 7, 6, 5, 4]
[-1, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

x, y =  3 0
x, y =  0 2
x, y =  1 1
x, y =  2 0

# bfs 수행 후 토마토가 모두 익을 때까지의 최소 날짜를 출력
# bfs 수행 후 graph 에 익지 않은 토마토(0)가 존재하기 때문에 -1 이 출력됨
-1

 

 

문제 해설

이 문제는 BFS 를 이용했을 때 매우 효과적으로 해결할 수 있다.

BFS 는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.

 

그러므로 (0, 0) 지점에서부터 BFS 를 수행하여 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.

그러면 그 노드의 값이 여태까지 방문(이동)한 노드의 수가 된다.

 

 

 

bfs 의 매개변수를 (x, y) 가 아닌 queue로 넘긴 이유

예제 3번을 보면 쉽게 알 수 있다.

만약 특정 노드 (x, y) 로 넘긴다면 (0, 0) 이 가장 먼저 탐색된다.

bfs (0, 0) 수행 시 queue : (0, 0) → (1, 0) → (2, 0) → (3,0) → (2,1) → ... → (2, 5) → (3, 5) 순서로 탐색

# 특정 노드를 매개변수로 넘겨주는 잘못된 코드 예시

from collections import deque

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

for i in range(n):
    print(graph[i])

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        print('x, y = ', x, y)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx, ny))
                    for i in range(n):
                        print(graph[i])
                    
for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      bfs(i, j)

max = 0
for i in range(n):
    if max == -1:
        break
    for j in range(m):
        if graph[i][j] == 0:
            max = -1
            break
        if graph[i][j] > max:
            max = graph[i][j] - 1 # 익은 날짜를 1부터 시작했으니까 다시 빼줌
print(max)


###############################

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

[1, -1, 0, 0, 0, 0]
[0, -1, 0, 0, 0, 0]
[0, 0, 0, 0, -1, 0]
[0, 0, 0, 0, -1, 1]

# bfs(x, y) 수행

x, y =  0 0
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[0, 0, 0, 0, -1, 0]
[0, 0, 0, 0, -1, 1]

x, y =  1 0
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[3, 0, 0, 0, -1, 0]
[0, 0, 0, 0, -1, 1]

x, y =  2 0
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[3, 0, 0, 0, -1, 0]
[4, 0, 0, 0, -1, 1]

[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[3, 4, 0, 0, -1, 0]
[4, 0, 0, 0, -1, 1]

x, y =  3 0
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[3, 4, 0, 0, -1, 0]
[4, 5, 0, 0, -1, 1]

x, y =  2 1
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[3, 4, 5, 0, -1, 0]
[4, 5, 0, 0, -1, 1]

x, y =  3 1
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[3, 4, 5, 0, -1, 0]
[4, 5, 6, 0, -1, 1]

x, y =  2 2
[1, -1, 0, 0, 0, 0]
[2, -1, 6, 0, 0, 0]
[3, 4, 5, 0, -1, 0]
[4, 5, 6, 0, -1, 1]

[1, -1, 0, 0, 0, 0]
[2, -1, 6, 0, 0, 0]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 0, -1, 1]

x, y =  3 2
[1, -1, 0, 0, 0, 0]
[2, -1, 6, 0, 0, 0]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 7, -1, 1]

x, y =  1 2
[1, -1, 7, 0, 0, 0]
[2, -1, 6, 0, 0, 0]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 7, -1, 1]

[1, -1, 7, 0, 0, 0]
[2, -1, 6, 7, 0, 0]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 7, -1, 1]

x, y =  2 3

x, y =  3 3

x, y =  0 2
[1, -1, 7, 8, 0, 0]
[2, -1, 6, 7, 0, 0]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 7, -1, 1]

x, y =  1 3
[1, -1, 7, 8, 0, 0]
[2, -1, 6, 7, 8, 0]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 7, -1, 1]

x, y =  0 3
[1, -1, 7, 8, 9, 0]
[2, -1, 6, 7, 8, 0]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 7, -1, 1]

x, y =  1 4
[1, -1, 7, 8, 9, 0]
[2, -1, 6, 7, 8, 9]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 7, -1, 1]

x, y =  0 4
[1, -1, 7, 8, 9, 10]
[2, -1, 6, 7, 8, 9]
[3, 4, 5, 6, -1, 0]
[4, 5, 6, 7, -1, 1]

x, y =  1 5
[1, -1, 7, 8, 9, 10]
[2, -1, 6, 7, 8, 9]
[3, 4, 5, 6, -1, 10]
[4, 5, 6, 7, -1, 1]

x, y =  0 5
x, y =  2 5
x, y =  3 5

# 잘못된 최소날짜 출력
9

하지만 매개변수를 queue로 넘긴다면 익은 토마토가 있는 노드들 (0, 0), (3, 5) 가 가장 먼저 탐색된다.

bfs (queue) 수행 시 queue : (0, 0) → (3, 5)  → (1, 0) → (2, 5) → (2, 0) → (1, 5) → ... (3, 3) → (0, 2) 순서로 탐색

# bfs의 매개변수를 queue 로 넘긴 정답 코드 예시 결과

# 예제 3번
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

#graph
[1, -1, 0, 0, 0, 0]
[0, -1, 0, 0, 0, 0]
[0, 0, 0, 0, -1, 0]
[0, 0, 0, 0, -1, 1]

# bfs 수행

x, y =  0 0
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[0, 0, 0, 0, -1, 0]
[0, 0, 0, 0, -1, 1]

x, y =  3 5
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[0, 0, 0, 0, -1, 2]
[0, 0, 0, 0, -1, 1]

x, y =  1 0
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 0]
[3, 0, 0, 0, -1, 2]
[0, 0, 0, 0, -1, 1]

x, y =  2 5
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 3]
[3, 0, 0, 0, -1, 2]
[0, 0, 0, 0, -1, 1]

x, y =  2 0
[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 3]
[3, 0, 0, 0, -1, 2]
[4, 0, 0, 0, -1, 1]

[1, -1, 0, 0, 0, 0]
[2, -1, 0, 0, 0, 3]
[3, 4, 0, 0, -1, 2]
[4, 0, 0, 0, -1, 1]

x, y =  1 5
[1, -1, 0, 0, 0, 4]
[2, -1, 0, 0, 0, 3]
[3, 4, 0, 0, -1, 2]
[4, 0, 0, 0, -1, 1]

[1, -1, 0, 0, 0, 4]
[2, -1, 0, 0, 4, 3]
[3, 4, 0, 0, -1, 2]
[4, 0, 0, 0, -1, 1]

x, y =  3 0
[1, -1, 0, 0, 0, 4]
[2, -1, 0, 0, 4, 3]
[3, 4, 0, 0, -1, 2]
[4, 5, 0, 0, -1, 1]

x, y =  2 1
[1, -1, 0, 0, 0, 4]
[2, -1, 0, 0, 4, 3]
[3, 4, 5, 0, -1, 2]
[4, 5, 0, 0, -1, 1]

x, y =  0 5
[1, -1, 0, 0, 5, 4]
[2, -1, 0, 0, 4, 3]
[3, 4, 5, 0, -1, 2]
[4, 5, 0, 0, -1, 1]

x, y =  1 4
[1, -1, 0, 0, 5, 4]
[2, -1, 0, 5, 4, 3]
[3, 4, 5, 0, -1, 2]
[4, 5, 0, 0, -1, 1]

x, y =  3 1
[1, -1, 0, 0, 5, 4]
[2, -1, 0, 5, 4, 3]
[3, 4, 5, 0, -1, 2]
[4, 5, 6, 0, -1, 1]

x, y =  2 2
[1, -1, 0, 0, 5, 4]
[2, -1, 6, 5, 4, 3]
[3, 4, 5, 0, -1, 2]
[4, 5, 6, 0, -1, 1]

[1, -1, 0, 0, 5, 4]
[2, -1, 6, 5, 4, 3]
[3, 4, 5, 6, -1, 2]
[4, 5, 6, 0, -1, 1]

x, y =  0 4
[1, -1, 0, 6, 5, 4]
[2, -1, 6, 5, 4, 3]
[3, 4, 5, 6, -1, 2]
[4, 5, 6, 0, -1, 1]

x, y =  1 3

x, y =  3 2
[1, -1, 0, 6, 5, 4]
[2, -1, 6, 5, 4, 3]
[3, 4, 5, 6, -1, 2]
[4, 5, 6, 7, -1, 1]

x, y =  1 2
[1, -1, 7, 6, 5, 4]
[2, -1, 6, 5, 4, 3]
[3, 4, 5, 6, -1, 2]
[4, 5, 6, 7, -1, 1]

x, y =  2 3
x, y =  0 3
x, y =  3 3
x, y =  0 2

# bfs 수행 후 토마토가 다 익을 때까지의 최소 날짜 출력
# 만약 bfs 의 매개변수를 큐로 주지 않고 특정 노드로 줬다면, 탐색 순서가 올바르지 않아 9가 출력된다.
6

 

출처

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

 

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 1753번 : 최단경로 / 다익스트라(Dijkstra) / 파이썬 Python  (0) 2021.07.29
[백준] 11653번: 소인수 분해 / 파이썬  (1) 2021.07.29
[백준] 2178번 : 미로 탐색 / BFS / 파이썬 Python  (0) 2021.06.22
[백준] 1012번 : 유기농 배추 / DFS / 파이썬 Python / 런타임에러  (0) 2021.06.21
[백준] 2667번 : 단지번호붙이기 / DFS / 파이썬 Python  (0) 2021.06.16

'코딩테스트/백준'의 다른글

  • 현재글[백준] 7576번 : 토마토 / BFS / 파이썬 Python

관련글

댓글

티스토리툴바