[알고리즘] DFS/BFS - 백준 1260번/2606번

1260번 - https://www.acmicpc.net/problem/1260

DFS와 BFS

 

접근 방법

- 인접행렬 방식으로 작성

- 처음 코드 작성 후 제출시 런타임에러(RecursionError)

--> DFS의 재귀함수가 너무 많이 돌아가 발생

- 코드 수정 후 틀린 부분 --> DFS의 노드에서 돌아갈 곳이 없을 때의 반복을 구현하지 않았다..

- 수정해서 통과 !

 

import copy
from collections import deque


def dfs(graph, v):
    if graph[v][v] != -1:
        print(v + 1, end=' ')
        for i in range(len(graph)):
            graph[i][v] = -1  # 방문했다
    while True:
        node = graph[v].index(1) if 1 in graph[v] else None# 방문하지 않은 연결된 노드 가져오기
        if node is None:
            return
        graph[v][node] = -1  # 방문했다
        dfs(graph, node)
    return


def bfs(graph, firstV):
    queue = deque([firstV])
    graph[firstV][firstV] = -1
    for i in range(len(graph)):
        graph[i][firstV] = -1  # 방문했다
    while queue:
        v = queue.popleft()
        print(v + 1, end=' ')
        while True:
            try:
                node = graph[v].index(1)  # 방문하지 않은 연결된 노드 가져오기
            except:
                break
            if graph[node][node] != -1:
                queue.append(node)
                for i in range(len(graph)):
                    graph[i][node] = -1  # 방문했다


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

# 인접행렬로 그래프 표현 ( 연결X --> 0 / 연결O --> 1)
graph = [[0 for i in range(N)] for j in range(N)]

for i in range(M):
    edge1, edge2 = list(map(int, input().split()))
    graph[edge1 - 1][edge2 - 1] = 1
    graph[edge2 - 1][edge1 - 1] = 1

dfs(copy.deepcopy(graph), V - 1)
print()
bfs(copy.deepcopy(graph), V - 1)

 

---

2606번 - https://www.acmicpc.net/problem/2606

바이러스

 

접근 방법

- BFS로 작성

- 인접리스트 - 2차원 리스트로 작성

DFS로 작성하면 더 간결해보임(딕셔너리로도 구현 가능할 듯)

 

import copy
from collections import deque


def bfs(graph, visited, V=1 ):
    cnt = -1
    queue = deque([V])
    visited[V] = True
    while queue:
        virus = queue.popleft()
        cnt += 1
        while len(graph[virus]):
            nextvirus = graph[virus].pop()
            if visited[nextvirus] is False:
                queue.append(nextvirus)
                visited[nextvirus] = True
    return cnt


N = int(input())
M = int(input())

# 인접리스트로 그래프 표현 ( 0번째 인덱스 사용 X )
graph = [[] for _ in range(N + 1)]

for i in range(M):
    edge1, edge2 = list(map(int, input().split()))
    graph[edge1].append(edge2)
    graph[edge2].append(edge1)

visited = [False] * (N+1)
print(bfs(graph, visited, 1))

 

코드 정리 : https://github.com/mingxoxo/Algorithm/tree/master/baekjoon

GitHub - mingxoxo/Algorithm: 알고리즘