백준 1260 - DFS와 BFS

문제

알고리즘 분류)

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

풀이

백준의 단계별문제의 그래프 문제로 가장 기본적으로 나와있는 문제이다

제일 첫번째로 입력으로 주어진 간선정보를 행렬로 나타낸다.
연결되어 있는 정점은 1, 그렇지않으면 0으로 표시한다
양방향이므로 대각선으로 대칭을 이루게 된다

예) 1 2 , 1 3 , 1 4 , 2 4 , 3 4 일 경우

정점	1	2	3	4	5
1	0	1	1	1	0
2	1	0	0	1	0
3	1	0	0	1	0
4	1	1	1	0	0
5	0	0	0	0	0

다음, 방문여부를 담을 길이N의 배열(visited)을 선언해준다
정점을 방문했다면 1로, 아직 방문하지 않았다면 0으로 처리될 것이다

• 깊이우선탐색)
  반복문으로 정점 1부터~5까지 탐색을 한다
  만약 아직 방문을 안했고(visited=0) , 연결된 정점일시(array[정점1][정점2]==1)
  재귀호출로 dfs를 실행한다

  step1)
  dfs(1) , 1을 프린트
  array[1][1] = 0 이므로 탐색하지 않는다

  step2)
  array[1][2] = 1 이므로 탐색한다
  dfs(2) , 2를 프린트 , 재귀depth:1

  step3) 앞에서 정점2를 탐색했으므로 2에서 시작
  array[2][1] = 1 이지만, 앞에서 방문했으므로 탐색하지 않는다

  step4)
  array[2][2] = 0
  array[2][3] = 0 이므로 탐색하지않는다

  step5)
  array[2][4] = 1 이므로 탐색한다
  dfs(4) , 4를 프린트 , 재귀depth:2
  . . .

• 너비우선탐색)
  탐색을 하는 조건은 깊이우선탐색과 같지만 bfs를 호출하면 곧바로 정점을 print하는 대신
  큐에 넣어 큐가 빌때까지 bfs를 진행한다
  정점을 탐색하면 해당 정점에서 정점의 끝까지 큐에 append 해준뒤 방문처리를 한다
  

---

소스코드

python)

import sys

def dfs(v):
  visited[v] = True
  print(v, end=' ')
  for i in range(1,N+1):
      if not visited[i] and array[v][i]:
          dfs(i)
def bfs(v):
  visited[v] = True
  queue.append(v)
  while queue:
      v=queue.pop(0)
      print(v,end=' ')
      for i in range(1,N+1):
          if array[v][i] and not visited[i]:
              queue.append(i)
              visited[i] = True

N,M,V = map(int,input().split())
array = [[0 for col in range(N+1)] for row in range(N+1)]
queue=[]    

for _ in range(M):
  i,j = map(int,sys.stdin.readline().split())
  array[i][j],array[j][i] = 1,1

visited = [False]*(N+1)
dfs(V)
print('')
visited = [False]*(N+1)
bfs(V)