[JAVA][백준 1260] DFS와 BFS - 인접 행렬로 풀기

사이트명	백준
문제 링크	www.acmicpc.net/problem/1260
주요 알고리즘	그래프, DFS, BFS
사용 언어	Java 자바
설명이 장황합니다.. 도움되는 것만 파악하세요 :-)

1. 문제

2. 입력 / 출력

---

3. 풀이

3-1. 생각 노트

이전에 인접 행렬로 풀었던 것을 다시 보며 리뷰를 진행하려 한다.

특히 인접 리스트로 풀 땐, 가장 작은 노드부터 방문한다는 정렬 조건 때문에 고민했는데, 이전에 푼 코드를 보니 정렬에 대한 고민의 흔적이 없었다..

 

그 이유는, 이미 행렬의 경우 1부터 순차적으로 접근하기 때문에 작은 노드부터 접근하게 된다.

반면, 리스트의 경우 내가 삽입한 순서대로 들어가기 때문에 정렬이 필요하다.

 

그림으로 표현하면 아래와 같다.

 

 

 

---

 

3-2. 변수명

변수명	설명
int[][] graph	인접 행렬을 표시하기 위한 2차원 배열. DFS의 접근을 용이하게 하기 위해 전역 변수로 설정
boolean[] visited	방문 여부를 나타내는 visited배열. 전체 노드 수만큼 할당했다.

 

3-3. 코드 보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/*
 * 그래프의 인접도, 배열 형태로 표현
 * 행(x축)을 기준으로 열값을 하나씩 늘려가며 탐색(오른차순으로 확인)
 * 
 */

public class BOJ1260_DFS_BFS_행렬 {
	
	static int[][] graph;
	static boolean[] visited = new boolean[1001];	//입력 케이스 +1
	static int N, M;
	
	static Queue<Integer> q = new LinkedList<>();
	static StringBuilder st = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] token = br.readLine().split(" ");
		
		N = Integer.parseInt(token[0]);	//정점수	4
		M = Integer.parseInt(token[1]);	//간선수	5
		int V = Integer.parseInt(token[2]);	//탐색시작 정점	  1
		
		graph = new int[N+1][N+1];
		
		for (int i = 0; i < M; i++) {
			token = br.readLine().split(" ");
			int node1 = Integer.parseInt(token[0]);
			int node2 = Integer.parseInt(token[1]);
			
			//무향(양방향) 그래프
			graph[node1][node2] = 1;
			graph[node2][node1] = 1;
		}
		
		dfs(V);
		st.append("\n");
		Arrays.fill(visited, false);		//방문배열 초기화
		
		bfs(V);
		System.out.println(st);
		st.setLength(0);					//스트링 빌더 초기화
		Arrays.fill(visited, false);		//방문배열 초기화
		
//		for (int i = 1; i <= N; i++) {
//			for (int j = 1; j <= N; j++) {
//				System.out.print(graph[i][j]);
//			}
//			System.out.println();
//		}
		
	}
	
	private static void dfs(int v) {		//v : 1
		
		//들어오면 본인 방문 설정
		visited[v] = true;
		st.append(v).append(" ");
		
		//recursive
		for (int i = 1; i <= N; i++) {
			if(graph[v][i] == 1 && !visited[i]) { 		//관계가 있고, 방문을 안했으면
				dfs(i);
			}
		}
	}//dfs

	static void bfs(int v) {
		
		//시작하자마자 본인 값 q에 넣기(while 부분부터 제대로된 bfs시작
		q.add(v);
		visited[v] = true;
		
		while(!q.isEmpty()) {
			
			v = q.poll();
			st.append(v).append(" ");
			
			// 행이 고정된 상태에서 1부터 ~ N까지의 열 값을 넣어가며 체크(가로방향)
			for (int i = 1; i <= N; i++) {
				if(graph[v][i] == 1 && !visited[i]) {
					q.add(i);			//모든 값을 q에 넣고, 겉 while문으로 반복
					visited[i] = true;
				}
			}
		}
		q.clear();
	}//bfs
	
	

}

 

3-4. 마무리

 

이미 풀었던 문제라도, 리뷰하며 찬찬히 뜯어보면 내가 그당시 무슨 생각으로 풀었는지 얼추 짐작이 가능하다.

그런데 정렬에 대한 고민의 흔적이 안보이는 걸로 봐선, 그냥 풀었나보다 -_-