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

🥚문제

---

🥚입력/출력

---

🍳코드

# DFS와 BFS
from collections import deque

# DFS 함수
def dfs(graph, v, visited):
    stack = []
    if not visited[v]:
        print(v, end=' ')
    visited[v] = True
    # 인접 노드들 stack에 삽입
    for i in range(len(graph)-1, 0, -1): # 정점 번호가 작은 것을 먼저 방문
        if graph[v][i] == 1 and not visited[i]:
            stack.append(i)
    # stack이 비어있을 때 까지 dfs
    while stack:
        next = stack.pop()
        dfs(graph, next, visited)

# BFS 함수
def bfs(graph, v, visited):
    queue = deque()
    queue.append(v)
    while queue:
        next = queue.popleft()
        visited[next] = True
        print(next, end=' ')
        for i in range(len(graph)):
            # 인접 노드를 queue에 삽입
            if graph[next][i] == 1 and not visited[i]:
                if i not in queue:
                    queue.append(i)


# N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점의 번호
n, m, v = map(int, input().split())
# M개의 줄에 간선이 연결하는 두 정점의 번호
graph = [[0 for _ in range(n+1)] for __ in range(n+1)] # 정보를 저장할 graph
for _ in range(m):
    data = input().split()
    graph[int(data[0])][int(data[1])] = 1
    graph[int(data[1])][int(data[0])] = 1
# dfs, bfs 호출
visited = [False]*(n+1)# 방문 여부 체크
dfs(graph, v, visited)
print()
visited = [False]*(n+1)# 방문 여부 체크
bfs(graph, v, visited)

---

🧂아이디어

• matrix=[[0]*(N+1) for i in range(N+1)] 에 익숙해지기

• 다른 사람의 간결한 코드 보기

N,M,V=map(int,input().split())
matrix=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    matrix[a][b]=matrix[b][a]=1
visit_list=[0]*(N+1)

def dfs(V):
    visit_list[V]=1 #방문한 점 1로 표시
    print(V, end=' ')
    for i in range(1,N+1):
        if(visit_list[i]==0 and matrix[V][i]==1):
            dfs(i)

def bfs(V):
    queue=[V] #들려야 할 정점 저장
    visit_list[V]=0 #방문한 점 0으로 표시
    while queue:
        V=queue.pop(0)
        print(V, end=' ')
        for i in range(1, N+1):
            if(visit_list[i]==1 and matrix[V][i]==1):
                queue.append(i)
                visit_list[i]=0

dfs(V)
print()
bfs(V)

출처: https://velog.io/@i-zro/%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EC%BD%94%ED%85%8C-%EB%8C%80%EB%B9%84-DFSBFS-%EB%B0%B1%EC%A4%80-1260%EB%B2%88-DFS%EC%99%80-BFS

• DFS/BFS 문제를 풀었다는 데에 의의가 있지만 너무 지저분하다. 줄일 수 있는 부분들이 많았음.