글 읽기 - [1012] 파이썬 bfs 시간초과

opr8632 3년 전 1

dfs로 풀어본 후 연습삼아 bfs로도 풀어보는데 시간초과가 나네요,, 어떤 부분이 문제일까요?

from collections import deque

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


def bfs(x, y):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        graph[x][y] = 0
        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] == 1:
                    q.append((nx, ny))


t = int(input())
for _ in range(t):
    n, m, k = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        a, b = map(int, input().split())
        graph[a][b] = 1

    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                bfs(i, j)
                count += 1
    print(count)

adxx 3년 전 0

이미 방문했는지 안했는지 체크 안한거 아닐까요?

dfs로 푸신 코드도 확인해보니 방문 여부 확인하는 부분이 안보이는데 어떻게 푸신건지 설명 부탁드려도 될까요?

opr8632 3년 전 0

만약 x, y를 방문을 하게 되면 graph[x][y] = 0으로 대입하게 됩니다. 위 소스코드의 17번째 줄을 보시면 1인 경우만(=방문을 안한 경우만) 큐에 넣고 있고 dfs로 푼 코드도 마찬가지 기법을 사용했습니다.

adxx 3년 전 1

그럼 queue에 넣기전에 방문 표시를 해주세요

opr8632 3년 전 0

방문하게되면 1이었던 값이 0으로 바뀌게 되면서 다음부턴 방문할 수 없게 되는데, 이러면 자동으로 방문여부가 체크되지 않나요?

adxx 3년 전 1

중복방문을 할 수 있지 않을까요? 실제로 그렇게 동작하는 것 같구요

opr8632 3년 전 0

디버깅해보니 정말 중복 방문을 하네요... 다양한 방향에서 같은 좌표에 갈 수 있다는 점을 간과했습니다.

방문여부를 체크하는 리스트를 따로 만들어서 큐에 넣고 체크하는 코드로 바꾸어서 제출하니 시간초과가 나지 않았습니다 답변 정말 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.