[BAEKJOON] 토마토(7576)(python)

ivor·2022년 9월 19일
0

코딩테스트

목록 보기
3/10

문제

문제 링크


풀이

초기 아이디어 및 문제점

기본적으로 bfs를 이용해서 해결할 수 있는 문제이다.
몇 가지 주의해야 할 점을 나열해보자면

  1. 특정 익은 토마토(1) 하나에서만 시작되는 것이 아니라 '모든' 익은 토마토에서 동시다발적으로 영향력이 퍼져나간다.
  2. 토마토가 하나 이상 있는 경우만 입력으로 주어진다. 즉 입력이 모두 '-1'인 경우는 없다.

처음에 짠 코드는 다음과 같다.

import sys
from collections import deque

def bfs(graph, pos):
    q = deque([(p[0], p[1]) for p in pos])
    move = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + move[i][0]
            ny = y + move[i][1]
            
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue

            if graph[ny][nx] == -1:
                continue

            if graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                q.append((nx, ny))

    return max(max(graph)) - 1

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

ripe_tomatoes = [(x, y) for y in range(n) for x in range(m) if tomatoes[y][x] == 1]

days = bfs(tomatoes, ripe_tomatoes)
if [0 for y in range(n) for x in range(m) if tomatoes[y][x] == 0]:
    print(-1)
else:
    print(days)

문제에 주어진 예제는 모두 만족하였지만 제출 시 오답으로 나왔다.
deque를 사용해 시간 제한도 만족할 수 있었고 기본적인 bfs로 모든 토마토를 익힐 때까지 며칠이 걸리는지도 구할 수 있었다.
또 bfs가 완료된 후 graph 내에 0이 하나라도 있으면(즉 모든 토마토를 익게 할 수 없다면) '-1'을 반환하도록 만들기도 했다.

즉 로직 상에 문제는 없다고 판단했는데 어디서 틀렸는지 알 수 없었다.

반례를 찾아보던 중 문제점을 찾아낼 수 있었다.

2차원 배열에 대해 max를 수행하면 '첫번째 원소가 max인' 1차원 배열을 출력한다. 때문에 의도한 바대로 graph 내에서 가장 큰 값을 반환하도록 하려면 max(max(graph)) - 1max([max(row) for row in graph])로 바꿔야 한다.

정답 코드

최종 정답 코드는 다음과 같다.

import sys
from collections import deque

def bfs(graph, pos):
    q = deque([(p[0], p[1]) for p in pos])
    move = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + move[i][0]
            ny = y + move[i][1]
            
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue

            if graph[ny][nx] == -1:
                continue

            if graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                q.append((nx, ny))

    return max([max(row) for row in graph]) - 1

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

ripe_tomatoes = [(x, y) for y in range(n) for x in range(m) if tomatoes[y][x] == 1]

days = bfs(tomatoes, ripe_tomatoes)
if [0 for y in range(n) for x in range(m) if tomatoes[y][x] == 0]:
    print(-1)
else:
    print(days)
profile
BEST? BETTER!

0개의 댓글