[BOJ] DFS와 BFS ★

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

1260번: DFS와 BFS

1. 문제 이해 및 해결과정

 

 

2. 풀이방법

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int N, M,V;
int adj[1000 + 100][1000 + 100];
int visited[1000 + 100];

void DFS(int v) { //재귀

	cout << v << ' ';
	visited[v] = 1; //방문표시

	for (int i = 1; i <= N; i++) {
		if (visited[i] == 1 || adj[v][i] == 0)continue; //이미 방문했거나 연결안되어 있으면
		DFS(i);
	}


}
void BFS(int v) { //큐
	
	queue<int> q;
	
	q.push(v);
	visited[v] = 0; //dfs실행 한 후니까 0일때가 방문한 것

	while (!q.empty()) {
		v = q.front();
		cout << v << ' ';
		q.pop();
		for (int i = 1; i <= N; i++) {
			if (visited[i] == 0 || adj[v][i] == 0)continue; //이미 방문했거나 연결안되어있으면
			q.push(i);
			visited[i] = 0;
		}

	}

}
void InputData() {
	int x, y;
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		adj[x][y] = adj[y][x] = 1 ; //인접행렬 표시
	}
}
int main() {
	freopen("input.txt", "r", stdin);

	InputData();
	DFS(V);
	cout << "\n";
	BFS(V);

	return 0;
}

 

  2. [python] DFS,BFS

#DFS와 BFS
#https://www.acmicpc.net/problem/1260
import sys
from collections import deque
sys.stdin = open("input.txt","r")
input=sys.stdin.readline

def DFS(v):
    visited[v]=1 #방문표시
    print(v,end=' ')

    for i in range(1,n+1):
        if visited[i]==0 and adj[v][i]==1: #방문하지 않았고 연결되어 있으면
            DFS(i)

def BFS(v):
    Q=deque()
    Q.append(v)
    visited[v]=1

    while Q:
        v=Q.popleft()
        print(v,end=' ')
        for i in range(1, n + 1):
            if visited[i] == 0 and adj[v][i] == 1:  # 방문하지 않았고 연결되어 있으면
                Q.append(i)
                visited[i]=1


if __name__=="__main__":
    n,m,v=map(int,input().split())
    adj = [[0] * (n + 1) for _ in range(n + 1)]
    visited = [0] * (n + 1)
    for _ in range(m):
        s,e=map(int,input().split())
        adj[s][e]=adj[e][s]=1
    DFS(v)
    print()
    visited = [0] * (n + 1)
    BFS(v)

 

3. PYTHON BOJ 제출버전

import sys
from collections import deque

input = sys.stdin.readline

n, m, v = map(int,input().split())
adj = [[0]*(n+1) for _ in range(n+1)]
visited = [0] * (n+1)

for _ in range(m): #간선의 개수 
    s,e = map(int,input().split())
    adj[s][e] = adj[e][s] = 1


def DFS(v):
    visited[v] = 1 #방문 표시
    print(v, end = ' ')
    for i in range(1,n+1):
        if visited[i] == 0 and adj[v][i]==1: #아직 방문하지 않았고, 연결되어있으면
            DFS(i)

def BFS(v):
    visited = [0] * (n+1) #방문 배열 초기화 
    Q = deque()
    Q.append(v) #시작점
    visited[v]=1

    while Q:
        v = Q.popleft()
        print(v,end=' ')
        for i in range(1,n+1):
            if visited[i] == 0 and adj[v][i]==1: 
                Q.append(i)
                visited[i]=1

DFS(v) #시작점 
print()
BFS(v)

 

 

3. 오답원인

- 2번풀이 BFS에서 cur 과 v를 같은 변수로 했어야 되는데 틀려서 한참 찾았다... 

 

4. 알게된 점