백준 1260: DFS와 BFS 해설 (파이썬, node.js)

백준

 

✏️ 문제

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

1260번: DFS와 BFS

 

✏️ DFS와 BFS 개념

 

DFS와 BFS 개념부터가 가물가물해서 처음부터 정리하려고한다.

 

DFS(Depth-First-Search, 깊이우선탐색)

그림이 좋길래 가져와봤다.

탐색순서: 1->2->4->8->5->3->6->7 

 

(1) 탐색시작노드를 스택에 삽입하고 방문처리를 한다.

(2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.

(3) 더 이상 2번의 과정을 수행할 수 없을때까지 반복

 

DFS 소스코드 예제(나동빈 코드) - 재귀를 이용해 구현

# 노드의 연결정보를 표현
graph=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

#각 노드가 방문된 정보를 표현
visited = [False]*9

# 구현
def dfs(graph, v, visited):
  #현재노드 방문처리
  visited[v]=True
  print(v, end=' ')
  #현재노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

 

BFS(Breadth-First-Search, 너비우선탐색)

탐색순서:  1->2->3->5->4->8->6->7

(1) 탐색시작노드를 큐에 삽입하고 방문처리를 한다.

(2) 큐에서 노드를 꺼낸 뒤에 해당노드의 인접노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.

(3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

BFS 소스코드 예제(나동빈 코드) - 큐를 이용해 구현

from collections import deque

# 노드의 연결정보를 표현
graph=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

#각 노드가 방문된 정보를 표현
visited = [False]*9

#구현
def bfs(graph, start, visited):
  queue=deque([start])
  #현재노드 방문처리
  visited[start]=True
  #큐가 빌때까지 반복
  while queue:
    #큐에서 하나의 원소를 뽑아 출력
    v=queue.popleft()
    print(v, end=' ')
    #아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True

bfs(graph, 1, visited)

 

 

✏️ 백준 1260 풀이

입력값을 가지고 인접리스트를 만들고 dfs는 재귀, bfs는 큐를 이용해 풀이했다.

bfs의 경우 파이썬 리스트 자료구조를 이용해 pop(0)을 이용하면 O(N)의 시간복잡도를 가지기 때문에 collections 모듈의 deque를 이용해 O(1)의 시간복잡도로 풀이했다.

 

from collections import deque

# n=정점개수, m=간선개수, v=탐색시작점
N, M, V = list(map(int, input().split()))

# 인접영행렬
matrix = [[0]*(N+1) for i in range(N+1)]

#방문한곳체크기록할 리스트
visited_dfs = [0]*(N+1)
visited_bfs = [0]*(N+1)

# 입력받는 값에 대해 영형렬에 1삽입(인접리스트생성)
for i in range(M):
  a,b=map(int,input().split())
  matrix[a][b]=matrix[b][a]=1

def dfs(V):
  visited_dfs[V]=1
  print(V,end=' ')
  #재귀
  for i in range(1, N+1):
    if(visited_dfs[i]==0 and matrix[V][i]==1):
      dfs(i)

def bfs(V):
  #방문해야할 곳을 순서대로 넣을 큐
  queue=deque([V])
  visited_bfs[V]=1
  
  #큐안에 데이터없을때까지
  while queue:
    V=queue.popleft()
    print(V, end=' ')
    for i in range(1, N+1):
      if(visited_bfs[i]==0 and matrix[V][i]==1):
        queue.append(i)
        visited_bfs[i]=1

dfs(V)
print()
bfs(V)

 

node.js

자바스크립트 공부중이다.

function DFS(v){
  visited[v]=true;
  DFS_graph.push(v);
  for(let i=1; i<graph.length;i++){
    if(graph[v][i]===1 && visited[i]===false){
      DFS(i);
    }
  }
}

function BFS(v){
  let Queue=[];
  Queue.push(v);
  BFS_graph.push(v);

  while (Queue.length!==0){
    let deque=Queue.shift();
    visited2[deque]=true;
    for (let i=1;i<graph.length;i++){
      if (graph[deque][i]===1 && visited2[i]===false){
        visited2[i]=true;
        Queue.push(i);
        BFS_graph.push(i);
      }
    }
  }
  return;
}


const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
//전역변수
let graph=[];
let visited=[];
let visited2=[];
let DFS_graph=[];
let BFS_graph=[];

rl.on('line', function(line) {
  input.push(line);
}).on('close',function () {
  let [n,m,v]=input[0].split(' ').map((el)=>parseInt(el));
  input = input.slice(1);
  graph = Array.from(Array(n+1), () => Array(n+1).fill(0)); //0으로 2차원배열초기화

  for (let i of input){
    let [x,y]=i.split(' ').map((el)=>parseInt(el));
    graph[x][y]=graph[y][x]=1;
  }
  visited=new Array(n+1).fill(false);
  visited2=new Array(n+1).fill(false);
  DFS(v);
  BFS(v);
  console.log(DFS_graph.join(' '));
  console.log(BFS_graph.join(' '));
  process.exit();
});