문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
문제 분석
입력으로 주어지는 간선은 양방향이기 때문에,
이차원 행렬을 이용해 max[start][end] = 1이면 max[end][start] = 1 같이 적용
JAVA
DFS(깊이우선탐색)
트리의 루트에서 시작하여, 첫번째 자식 노드를 선택함. 자식이 자식을 가지고 있다면 첫번째 자식을 선택하고, 자식이 없는 노드에 도차하면 부모 노드로 거슬러 올라가고 부모 노드에 다음 자식이 있으면 그 쪽으로 이동. 루트의 마지막 노드까지 탐색하면 종료
되돌아가기 위해 스택 사용(재귀함수 호출로 묵시적인 스택 이용 가능)public static void dfs(int[][] mat, int start, boolean[] visited){ visited[start] = true; System.out.print(start + 1 + " "); for(int i = 0; i < mat.length; i++){ if(mat[start][i] == 1 && !visited[i]){ dfs(mat, i, visited); } } }
int[][] mat
edge 관계를 나타낸 이차원 행렬
ex) 간선이 연결하는 두 정점의 번호가 2, 3 이면 mat[2-1][3-1] = 1, mat[3-1][2-1] = 1
관계가 없으면 0
int start
트리의 루트를 가리킴, 정점의 번호
재귀호출할 때마다 루트가 바뀜
boolean[] visited
start의 노드는 방문이 되었기 때문에 visited[start] = true로 바꿈
for(int i = 0; i < mat.length; i++){
if(mat[start][i] == 1 && !visited[i]){
dfs(mat, i, visited);
}
}트리의 루트를 행으로 하고, 모든 열을 탐색
탐색 도중, 간선이 존재하고 정점 i의 노드가 방문되지 않았으면 재귀호출
BFS(너비우선탐색)
시작 정점으로부터 가까운 정점 먼저 방문 후, 멀리 있는 정점을 나중에 방문하는 탐색방법
큐를 사용하여 구현할 수 있음
하단 소스는 Deque를 이용, 재귀X 반복문Opublic static void bfs(int[][] mat, int start, boolean[] visited) { Deque<Integer> deque = new LinkedList<>(); deque.addLast(start); visited[start] = true; while(!deque.isEmpty()){ start = deque.removeFirst(); System.out.print(start + 1 + " "); for(int i = 0; i < mat.length; i++) { if (mat[start][i] == 1 && !visited[i]){ visited[i] = true; deque.addLast(i); } } } }
Deque<Integer> deque = new LinkedList<>();
deque.addLast(start);
visited[start] = true;재귀함수 호출이 아니기 때문에 먼저 start로 들어온 정점을 방문 처리한 후,
while문을 돌려야 한다.
while문의 조건은 !deque.isEmpty()로, start가 들어왔기 때문에 조건을 통과할 수 있다.
while(!deque.isEmpty()){
start = deque.removeFirst();
System.out.print(start + 1 + " ");
for(int i = 0; i < mat.length; i++) {
if (mat[start][i] == 1 && !visited[i]){
visited[i] = true;
deque.addLast(i);
}
}
}bfs는 먼저 가까이에 있는 정점들을 방문하기 때문에, for문을 돌리면서 if문 조건을 만족하는 정점은 방문하도록 한다. 그 후, deque에 enqueue한다. while문을 돌려 dequeue 진행.
deque가 empty일 때 까지 이 과정 반복
Main
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int vCnt = sc.nextInt(); int eCnt = sc.nextInt(); int vStart = sc.nextInt(); int[][] mat = new int[vCnt][vCnt]; // 이차원 행렬(matrix) boolean[] visited = new boolean[vCnt]; int i, start, end; for(i = 0; i < eCnt; i++) { start = sc.nextInt(); end = sc.nextInt(); mat[start - 1][end - 1] = 1; // 배열의 인덱스는 0부터 시작하므로 -1 mat[end - 1][start - 1] = 1; } dfs(mat, vStart - 1, visited) // dfs 호출 System.out.println(); visited = new boolean[vCnt]; // dfs에서 모두 true로 되었으므로, 초기화 bfs(mat, vStart - 1, visited); // bfs 호출 }
실패 case
처음에 Main에서
int vCnt = 0; int eCnt = 0; int vStart = 0; //0으로 초기화 후 Scanner sc = new Scanner(System.in); vCnt = sc.nextInt(); // 입력 받아 저장 eCnt = sc.nextInt(); vStart = sc.nextInt();이렇게 코드를 작성했다가 런타임 에러가 발생했다.
입력받을 때는 선언과 동시에 입력받아야 하는 듯하다.
또한 백준에 제출할 때에는 클래스 이름을 Main으로 꼭 설정해야 한다.
그렇지 않으면 컴파일 에러가 발생한다.
PYTHON
입력 받기 & 초기화
n, m, start = map(int, input().split()) # 공백을 기준으로 3개 정수 입력 받음 mat = [[0] * n for _ in range(n)] # n*n 2차원 배열 for k in range(m): # 주어진 간선의 개수(m)만큼 입력 받음 i, j = map(int, input().split()) mat[i - 1][j - 1] = 1 mat[j - 1][i - 1] = 1 # 양방향이므로 반대편도 # 방문 배열 생성(초기엔 다 False로) visited = [False] * n
DFS
def dfs(mat, v, visited): # 재귀함수 visited[v] = True # 파라미터 v를 방문 O print(v+1, end = ' ') # 배열은 0부터 시작하므로 + 1해서 출력 for i in range(len(mat[v])): # mat[v]의 배열의 개수(n)만큼 비교 if visited[i] != True and mat[v][i] == 1: # 간선의 관계에 있고, 방문하지 않았으면 재귀함수 호출 dfs(mat, i, visited)
BFS
from collections import deque # 큐 구현을 위해 deque 라이브러리 사용 def bfs(mat, v, visited): queue = deque([v]) # 시작 vertex를 enqueue하면서 큐 생성 visited[v] = True # 시작 vertex를 방문처리하고, while문으로 while queue: v = queue.popleft() # dequeue print(v + 1, end = ' ') for i in range(len(mat[v])): if visited[i] != True and mat[v][i] == 1: visited[i] = True queue.append(i)
dfs(mat, start - 1, visited) # dfs 함수 호출
visited = [False] * n # 방문 배열 다시 False로 초기화
print()
bfs(mat, start - 1, visited) # bfs 함수 호출파이썬으로 알고리즘 공부하는 건 처음인지라 입출력에서 막혔다
mat = [[0] * n for _ in range(n)] 와
mat =[[0] *n] * n의 차이가 뭐지... ?
입출력 공부해야겠다
