[백준] 1260번 - DFS와 BFS

DFS/BFS 개념에 대한 감을 잡기 위해 백준 단계벌 풀어보기의 DFS와 BFS 문제들을 풀어보려고 했다. 그런데 1260번 문제는 노드를 기준으로 인접한 노드 정보를 주지 않고 간선을 기준으로 인접한 노드 정보를 주는 문제였다.

작성한 코드

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

visited = [False] * (n + 1)

print(lines, visited)

def dfs(lines, v, visited):
  # 현재 노드가 방문하지 않은 노드라면
  if visited[v] == False:
    # 해당 노드를 방문 처리
    visited[v] = True
    print(v, end = ' ')
    

여기까지 쓰고 방문한 노드에서 인접한 노드를 판별하는 방법이 안 떠올라서 포기 ㅎ...
다른 사람들 코드를 보면서 공부하는 게 낫겠다 싶었다.

수정한 코드

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()) # 해당 간선에 연결된 노드를 a, b에 담는다
    matrix[a][b] = matrix[b][a] = 1 # 2차원 배열에 연결 정보(?)를 담는다
visited = [0] * (n + 1) # 방문한 노드 담기 위한 리스트

def dfs(v):
    visited[v] = 1 # 방문한 노드는 1로 표시
    print(v, end = ' ')
    for i in range(1, n + 1):
        if(visited[i] == 0 and matrix[v][i] == 1):
            dfs(i)

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

dfs(v)
print()
bfs(v)

마저 코드 공부하기

문제 출처
https://www.acmicpc.net/problem/1260

참고
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