• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

BFS 개인적으로 작성해본 코드에서 질문이 있습니다.

22.01.30 20:51 작성 조회수 128

0

import sys

from collections import deque

#sys.stdin=open("input.txt", "r")

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

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

sys.setrecursionlimit(10**6)

 

n,m = map(int, input().split())

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

q = deque()

answer = []

count = 0

flag = 1

 

 

def bfs():

    global count

    while q:

        size = len(q)

        for j in range(size):

            now = q.popleft()

            for i in range(4):

                x = now[0] + dx[i]

                y = now[1] + dy[i]

                if 0 <= x < m and 0 <= y < n and graph[x][y] == 0:

                    q.append((x,y))

                    graph[x][y] = 1

        count += 1

 

 

def chk(graph):

    global flag

    for i in range(m):

        for j in range(n):

            if graph[i][j] == 0:

                flag = 0

 

for i in range(m):

    for j in range(n):

        if graph[i][j] == 1:

            q.append((i,j))

            

bfs()

chk(graph)

if flag == 0:

    print(-1)

else:

    print(count-1)

 

 

        

         위와 같이 코드를 작성하였을때 모두 통과가 됩니다.

하지만 저는 궁금한점이, 왜 마지막 출력을 할때 count-1 을 해야 찾고자 하는 결과와 같아 질까요?? 
전 한개의 레벨을 마치면 count 를 올려주는 식으로 코드를 짜봤습니다.

답변 0

답변을 작성해보세요.

답변을 기다리고 있는 질문이에요.
첫번째 답변을 남겨보세요!