BOJ 1260번 - DFS와 BFS

난이도

---

실버 III

 

 

 

풀이

---

완전탐색 중 그래프 탐색 문제였다.

dfs는 재귀를 이용해서 구현하였고, bfs는 큐 자료구조를 이용해서 구현하였다.

 

import sys

input=sys.stdin.readline

N,M,V=map(int,input().split())
graph=[[0 for _ in range(N+1)] for _ in range(N+1)]
visited1=[False for _ in range(N+1)]
visited2=[False for _ in range(N+1)]

for _ in range(M):
    x,y=map(int,input().split())
    graph[x][y]=1
    graph[y][x]=1

def dfs(v):
    print(v,end=" ")
    visited1[v] = True

    for i in range(1,N+1):
        if graph[v][i]==1 and visited1[i]==False:
            dfs(i)


def bfs(v):
    que=list()
    que.append(v)
    visited2[v]=True

    while len(que)!=0:
        point=que.pop(0)
        print(point,end=" ")
        for i in range(1,N+1):
            if graph[point][i]==1 and visited2[i]==False:
                que.append(i)
                visited2[i] = True

dfs(V)
print("")
bfs(V)

 

 

기억해야할 것

그래프에서 정점이 1로 시작하는 경우는 꼭 N+1로 그래프 배열 만들어주기

파이썬에서 큐 자료구조 구현법

 

 

문제 링크

---

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

1260번: DFS와 BFS