[C, python] 백준 1260번 : DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

풀이

약 1년 전에 풀었던 문제지만 예전에 짰던 코드를 다시 보게 되었습니다

예전에 작성한 코드라 변수명이 마음에 들지 않는 부분들도 있어요ㅎㅎ

이번에 복습을 하면서 원래 c로 짰던 코드를 파이썬으로 다시 짜 보았습니다

파이썬을 제대로 공부해본적이 없어서 파이썬으로 짰다기 보다는 c를 파이썬으로 바꾼 느낌으로 코드를 작성한 것 같아서 아쉽네요

노트북에 있는 파이썬이 python2라 어쩌다보니 2로 작성하게 되었지만 다음부터는 3을 받아서 작성할 계획입니다

파이썬에서 range가 익숙하지 않아 어디가 틀렸는지 한참을 고민했습니다

파이썬에서 range는 (시작, 끝나고 다음 위치) 입니다

(시작, 끝) 이라고 생각하고 풀어 마지막 원소를 range에 포함시키지 못했네요

ex) range(2,5) = [2,3,4] 

또한 range를 1씩 증가시키는 것이 아니라 다른 수 혹은 음수만큼 변경하고 싶을 때에는

(시작, 끝나고 다음 위치, 변경시키고 싶은 양)을 넣어주면 됩니다

ex) range(5,1,-1) = [5,4,3,2]

C와 python 모두 같은 logic을 이용해서 풀어보았습니다

DFS는 stack, BFS는 queue를 이용했습니다

C++

#include <stdio.h>
#include <queue>
#include <stack>
using namespace std;
 
int arr[1005][1005];
int ch[1005];
int ch1[1005];
 
int main() {
    int n, m, k, now;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int temp1, temp2;
        scanf("%d %d", &temp1, &temp2);
        arr[temp1][temp2] = 1;
        arr[temp2][temp1] = 1;
    }
 
    //DFS
    stack <int> st;
    st.push(k);
    while (!st.empty()) {
        int now = st.top();
        st.pop();
        if (ch[now] == 0) {
            printf("%d ", now);
        }
        ch[now] = 1;
        for (int i = n; i >= 1; i--) {
            if (arr[now][i] == 1 && ch[i] != 1) {
                st.push(i);
            }
        }
    }
 
    printf("\n");
 
    //BFS
    queue <int> que;
    que.push(k);
    ch1[k] = 1;
    now = k;
 
    while (!que.empty()) {
        printf("%d ", que.front());
        now = que.front(); // 지금위치확인
        que.pop();  // pop
        for (int i = 1; i <= n; i++) {
            if (arr[now][i] == 1 && ch1[i] != 1) {
                que.push(i);
                ch1[i] = 1;
            }
        } // 방문체크하기
    }
    printf("\n");
    return 0;
}

python

#create a 1005 x 1005 matrix of zeroes
 
arr = [[0 for i in range (1005)] for j in range(1005)]
 
#create two 1005 matrix of zeroes
 
DFS_check = [0]*1005
BFS_check = [0]*1005
 
N,M,V = map(int,raw_input().split())
 
for i in range (int(M)):
    a,b = map(int,raw_input().split())
    arr[a][b] = 1
    arr[b][a] = 1
 
#DFS
stack = []
stack.append(V)
 
while stack :  
    now = stack[len(stack)-1]
    stack.pop()
    if DFS_check[now] == 0 :
        print now,
    DFS_check[now]=1
    for i in range(N,0,-1) :
        if arr[now][i] == 1 and DFS_check[i] != 1 :
            stack.append(i)
print
 
#BFS
queue = []
queue.append(V)
BFS_check[V]=1
now = V
while queue :
    now = queue[0]
    print queue[0],
    queue.pop(0)
    for i in range(1,N+1) :
        if arr[now][i] == 1 and BFS_check[i] != 1 :
            queue.append(i)
            BFS_check[i]=1
    
 

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