7576번 풀이 코드 관련 질문

안녕하세요 선생님. 7576번 토마토 문제를 풀기 위해 코드를 짜서 제출했는데 자꾸 틀렸다고 처리가 되어서 어디가 문제인지 궁금하여 질문드리려 합니다. time matrix 대신에 visit matrix를 쓰는거 말고는 예시답안과 거의 일치하는것 같은데 어디가 문제일까요?

import sys
from collections import deque


def bfs(cands):
    global data, N, M, min_dist, dx, dy
    
    visit = [[False] * M for _ in range(N)]
    
    q = deque()
    for (i,j) in cands:
        q.append([i,j,0])
        visit[i][j] = True
    
    while q:
        x,y,dep = q.popleft()
        min_dist[x][y] = min(min_dist[x][y], dep)

        for di, dj in zip(dx,dy):
            ni = x + di
            nj = y + dj
            
            if (0<= ni < N) and (0<=nj<M) and (not visit[ni][nj]) and (data[ni][nj] == 0):
            
                q.append([ni,nj,dep+1])
                visit[ni][nj] = True

dx = [0,1,0,-1]
dy = [1,0,-1,0]
M, N = map(int, input().split())

data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

min_dist = [[1e6]*M for _ in range(N)]
cands = []
for i in range(N):
    for j in range(M):
        if data[i][j] == 1:
            cands.append((i,j))
        if data[i][j] == -1:
            min_dist[i][j] = -1
bfs(cands)


val = max(max(min_dist))
if val == 1e6:
    print(-1)
else:
    print(val)

안녕하세요, purplejay님!

코드를 살펴본 결과, 올바른 풀이로 코드를 작성하신 거 같습니다.

단, max 함수에 대해 오해를 하시고 사용하신 것 같습니다.

max 함수의 공식 문서를 살펴보면, 원소 중에서 가장 큰 원소를 반환한다고 나와 있습니다.

따라서, 2차원 리스트를 max 함수에 넣는다면 가장 큰 값들로 이루어진 1차원 리스트가 나오는 것이 아닌, 1차원 리스트 중에서 가장 큰 리스트가 반환이 됩니다.

예를 들자면, max([[0, 1, 2], [1, 0, 1]])의 결과는 [2, 1]이 아닌, [1, 0, 1] 이라는 것입니다.

즉, [0, 1, 2]과 [1, 0, 1] 중에서 [1, 0, 1]이 더 크므로 [1, 0, 1]을 반환한 것이죠.

리스트의 크기 비교는 인덱스가 낮은 원소가 더 높으면 크기가 크다고 생각하시면 됩니다.

즉, [1, 1, 1, 2, 1]이 [1, 1, 1, 1, 10]보다 큰 것이죠.

두 리스트의 크기 비교에 관한 자세한 설명은 여기를 참고해세요 :)

질문자님이 의도하신 대로 max 함수를 이용하려면 max(max(md) for md in min_dist) 와 같이 사용하시면 될 것 같습니다. 이를 고쳐 코드를 작성하면 아래와 같이 작성할 수 있겠네요.

import sys
from collections import deque


def bfs(cands):
    global data, N, M, min_dist, dx, dy
    
    visit = [[False] * M for _ in range(N)]
    
    q = deque()
    for (i, j) in cands:
        q.append([i, j, 0])
        visit[i][j] = True
    
    while q:
        x, y, dep = q.popleft()
        min_dist[x][y] = min(min_dist[x][y], dep)

        for di, dj in zip(dx,dy):
            ni = x + di
            nj = y + dj
            
            if (0 <= ni < N) and (0 <= nj < M) and (not visit[ni][nj]) and (data[ni][nj] == 0):
                q.append([ni, nj, dep + 1])
                visit[ni][nj] = True


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

M, N = map(int, input().split())

data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

min_dist = [[1e6] * M for _ in range(N)]
cands = []
for i in range(N):
    for j in range(M):
        if data[i][j] == 1:
            cands.append((i, j))
        if data[i][j] == -1:
            min_dist[i][j] = -1

bfs(cands)

val = max(max(md) for md in min_dist) # 고친 부분

print(-1 if val == 1e6 else val)

질문에 대해 만족스러운 답변이 되었기를 바랍니다!

추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

5점 수강평을 남겨주시면 향후 더 나은 강의를 만드는 데 큰 도움이 됩니다. 🌟

인프런 커뮤니티 질문&답변