[백준/BOJ] 1260번 : DFS와 BFS (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

1260번: DFS와 BFS

---

- 문제 -

 

난이도 실버 2 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

이번 문제는 DFS와 BFS를 공부한 사람이라면 어렵지 않게 풀 수 있는 문제이다. 이 부분을 여기서 설명하기엔 어렵기도 한 부분이고, 짧게 설명이 되는 부분이기에 필자가 만약 공부 글을 올리게 되면 그걸 첨부 하거나 다른 사람들이 올려둔 블로그 글을 참고하자.

 

코드를 보자.

---

-풀이-

 

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

public class Main {
	//DFS에 쓰일 이차원 배열
	static int[][] Dgraph = new int[1001][1001];
	//BFS에 쓰일 이차원 배열
	static int[][] Bgraph = new int[1001][1001];
	static boolean[] Dvisit = new boolean[10001];
	//N은 DFS, BFS 메소드에도 사용되어야 하기 때문에 필드로 선언
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		
		//간선을 두개의 그래프 배열에 똑같이 저장해 준다.
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			Dgraph[u][v] = Dgraph[v][u] = 1;
			Bgraph[u][v] = Bgraph[v][u] = 1;
		}
		DFS(V);
		System.out.println();
		BFS(V);
	}
	
	public static void DFS(int node) {
		Dvisit[node] = true;
		System.out.print(node + " ");
		
		for(int i = 1; i <= N; i++) {
			if(!Dvisit[i] && Dgraph[node][i] == 1) {
				DFS(i);
			}
		}
	}
	
	public static void BFS(int node) {
		boolean[] Bvisit = new boolean[10001];
		Queue<Integer> que = new LinkedList<Integer>();
		Bvisit[node] = true;
		que.offer(node);
		
		while(!que.isEmpty()) {
			int P = que.poll();
			System.out.print(P + " ");
			
			for(int i = 1; i <= N; i++) {
				if(!Bvisit[i] && Bgraph[P][i] == 1) {
					Bvisit[i] = true;
					que.offer(i);
				}
			}
		}
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.