15. 토마토(BFS : Breadth First Search) 질문

Question

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. 라고 해서 m, n 을 입력 받았는데 왜 틀린지 모르겠습니다. 강사님 풀이에서 n, m이라고 받으신 이유도 모르겠습니다.... 아래 코드에서 제대로 array 받아오는 것 같은데 이유를 틀리는 이유를 모르겠습니다...! 강사님이 제공해주신 테스트 케이스는 다 통과하지만 백준에서는 틀리는 이유를 모르겠습니다...  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 # 받아온 array [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 1] 8 import sys sys.setrecursionlimit(10 ** 6) # sys.stdin=open("in5.txt", "r") def valid_coord(x, y): if 0 <= x < m and 0 <= y < n: return True else: return False def print_array(array): for elem in array: print(elem) def bfs(): while queue: # tmp_len = len(queue) # for _ in range(tmp_len): temp = queue.popleft() temp_dis = dis[temp[0]][temp[1]] for dx, dy in zip(dxs, dys): nx = temp[0] + dx ny = temp[1] + dy # 익지 않은 상태이거나 유효한 좌표일 때 if valid_coord(nx, ny) and arr[nx][ny] == 0: queue.append((nx, ny)) arr[nx][ny] = 1 dis[nx][ny] = temp_dis + 1 if __name__ == '__main__': from collections import deque n, m = map(int, input().split()) arr = [] for _ in range(m): arr.append(list(map(int, input().split()))) dis = [] for _ in range(m): dis.append([0] * n) dxs = (-1, 1, 0, 0) dys = (0, 0, -1, 1) # print_array(arr) # print('----') # print_array(dis) queue = deque() for i in range(m): for j in range(n): if arr[i][j] == 1: queue.append((i, j)) bfs() # print_array(dis) # arr에서 0을 발견하면 flag = False로 설정 flag = True for i in range(m): for j in range(n): if arr[i][j] == 0: flag = False result = 0 if not flag: print(-1) else: result = max(max(dis)) print(result)

김태원 · Answer

안녕하세요^^ 문제을 설명대로 m, n으로 받아야 하는데 제가 착각하고 n, m으로 받고 가로 크기를 n으로 세로 크기를 m으로 해서 푼 것 같습니다. 이건 문제될 답이 안나오는 것과는 상관은 없습니다. 아래와 같이 코치니 통과됩니다. import sys def valid_coord(x, y): if 0 <= x < m and 0 <= y < n: return True else: return False def bfs(): while queue: # tmp_len = len(queue) # for _ in range(tmp_len): temp = queue.popleft() temp_dis = dis[temp[0]][temp[1]] for dx, dy in zip(dxs, dys): nx = temp[0] + dx ny = temp[1] + dy # 익지 않은 상태이거나 유효한 좌표일 때 if valid_coord(nx, ny) and arr[nx][ny] == 0: queue.append((nx, ny)) arr[nx][ny] = 1 dis[nx][ny] = temp_dis + 1 if __name__ == '__main__': from collections import deque n, m = map(int, input().split()) arr = [] for _ in range(m): arr.append(list(map(int, input().split()))) dis = [] for _ in range(m): dis.append([0] * n) dxs = (-1, 1, 0, 0) dys = (0, 0, -1, 1) # print_array(arr) # print('----') # print_array(dis) queue = deque() for i in range(m): for j in range(n): if arr[i][j] == 1: queue.append((i, j)) bfs() # print_array(dis) # arr에서 0을 발견하면 flag = False로 설정 flag = True for i in range(m): for j in range(n): if arr[i][j] == 0: flag = False result = 0 if not flag: print(-1) else: for i in range(m): for j in range(n): if dis[i][j]>result: result=dis[i][j] print(result)