[BOJ] 1260번: DFS와 BFS

계속 미뤄놨던 DFS/BFS 개념을 공부한 후 백준에서 가장 기본적인 문제로 보이는 걸 풀어봤는데 여러 번의 시도 끝에 어찌저찌 맞았다. 하지만 위의 사진처럼 정답까지 가는 과정이 꽤 험난했기 때문에 코드를 복기해보려고 한다.

---

문제

 

입출력 예시

 

아이디어 흐름

코드의 큰 틀은 아래처럼 생각했다.

 

1) 그래프 형태 표현 방법? 2차원 배열 형태로 만들기

2) DFS 구현? 스택 구조나 재귀 함수 사용

3) BFS 구현? 큐 사용

 

 

런타임 에러

1) AttributeError

알고리즘 오랜만에 풀었더니 나도 모르는 사이에 까먹었는지 input 함수에 괄호를 안 썼다!^^

 

2) TypeError

사실 타입에러는 정확하게 어디서 난 건지 아직도 모르겠다. int를 써야하는데 char를 썼다던가 이럴 때 나는 에러라는데 이유는 못 찾았고 틀렸으니까 고쳐야겠다 이 생각이 컸던 것 같다.

 

시간 초과

# DFS
    for j in range(1, n+1):
        # 출발점 v의 인접노드이지만 방문한 적이 없는 노드
        if visited[j] == 0 and adjMatrix[v][j] == 1:
            dfs(j)
            
 # BFS
     while q:
        v = q.popleft()

        print(v, end=' ')

        # 방문 처리 되지 않은 인접 노드 모두 큐에 삽입
        for k in range(1, n+1):
            if k not in visited and adjMatrix[v][k] == 1:
                q.append(k)
                visited[k] = 1

재귀 때문에 그런가 싶어서 재귀 깊이를 더 깊게 설정하려다가 https://hjp845.tistory.com/32 이 글을 보고 노드 확인, 방문 체크 순서를 바꿔주었다.

 

출력 초과

BFS에서 무한루프 걸렸을 때 출력 초과였다.

 

완전히 틀린 경우

이것 때문에 고민을 정말 많이 했다. 예제 입력 2를 넣으면 BFS 출력 결과는 3 1 4 2 5가 나와야 하는데 계속 3 1 4까지만 나와서 왜 끝까지 탐색을 못할까 이 생각을 계속 했다.

 

최종 코드

위에 적은 에러들을 하나씩 해결하면서 제출한 최종 코드는 아래와 같다.

import sys

from collections import deque

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

# 인덱스 헷갈리지 않게 하려고 (n+1)*(n+1) 크기의 인접행렬 생성
adjMatrix = [[0]*(n+1) for _ in range(n+1)]

# 방문 체크용 배열 생성
visited = [0]*(n+1)

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    
    # 양방향 연결을 의미
    adjMatrix[a][b] = adjMatrix[b][a] = 1

def dfs(v):
    visited[v] = 1

    print(v, end=' ')

    for j in range(1, n+1):
        # 출발점 v의 인접노드이지만 방문한 적이 없는 노드
        if adjMatrix[v][j] == 1 and visited[j] == 0 :
            dfs(j)


def bfs(V):
    bfsVisited = [V]

    q = deque() # 큐 생성
    q.append(V) # 방문 처리한 노드는 큐에 삽입

    while q:
        pop = q.popleft()
        print(pop, end=' ')

        # 방문 처리 되지 않은 인접 노드 모두 큐에 삽입
        for k in range(len(adjMatrix[V])):
            if adjMatrix[pop][k] == 1 and (k not in bfsVisited):
                q.append(k)
                bfsVisited.append(k)

dfs(v)
print()
bfs(v)

 

정리

모든 코드들의 아이디어 흐름은 동일했고 최종 코드와 이전 코드들의 큰 차이점을 정리해보면

 

1) 방문 체크용 배열 사용 방법

전역 변수로 방문 검사를 위한 배열을 하나 만들고 DFS에서는 방문한 노드 번호와 동일한 인덱스 값을 1로, BFS에서는 이미 1로 바뀐 인덱스들이 있기 때문에 방문했을 경우 0으로 바꿔주는 방식을 사용했었다. 근데 이 방법으로 하니까 내가 헷갈려서 BFS는 함수 안에서 방문 체크용 배열을 따로 만들었다.

 

2) for k in range(len(adjMatrix[V]))

for k in range(1, n+1) 이걸로 계속 코드를 짜다가 BFS에서만 값이 제대로 안 나오니까 다른 분들의 BFS 코드와 내 걸 하나하나 비교하면서 고친 부분이다. 내가 이해한 방식은 '노드 V와 연결된 인접 노드 수만큼 반복문을 돌린다' 는 것인데 맞게 이해한건지는 확신이 없다 😅

 

앞으로 문제를 많이 풀어봐야겠다.