[백준] 1260 : DFS와 BFS - JAVA

Benjamin·2022년 12월 14일

백준

BAEKJOON

목록 보기

22/70

문제분석

N의 최대는 1000, M의 최대는 10000이다.
DFS or BFS사용시 시간복잡도는 O(11000)인데, 각각 수행하므로 O(22000)이다.
이는 시간제한 2초안에 해결 가능하다.

작은 노드의 번호부터 탐색 = 인접 노드를 오름차순으로 정렬한 후 재귀 함수 호출

슈도코드

인접리스트 A 선언 
방문배열 visited 선언
N M V 입력받기
A, visited 초기화
for(N번 반복) {
	A의 원소 초기화
}
for(M번 반복) {
	두 노드 입력받기
    A의 각각에 삽입 
}

//DFS 수행
DFS(V)
방문배열 초기화
BFS(V)

DFS(V) {
	if(visited[V]) return
	방문배열 true로 체크
    bw.write(V)
    for(배열 속 각 리스트 조회) {
    	if(방문하지않았으면) DFS()
    }
    bw.flush()
}

BFS(V) {
	Queue<Integer> queue = new LinkedList<Integer>();
	if(visited[V]) return
	queue.add(V)
    visited[v] = true
    while(큐가 비어있을 때까지) {
    	queue.poll(V) & 출력 
        for(i : A[V}){
        	if(!visited[i]) {
            	queue.add(i)
                visited[i] = true
            }
        }
    }
}

Troubleshooting

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

public class Main {
static boolean[] visited;
static ArrayList<Integer>[] A;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		visited = new boolean[N+1];
		A = new ArrayList[N+1];
		for(int i=1; i<N+1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			A[start].add(end);
			A[end].add(start);
		}
		
		DFS(V);
		for(int i=1; i<N+1; i++) {
			visited[i] = false;
		}
		BFS(V);
	}
	
	public static void DFS(int V) {
		System.out.println(V + " ");
		if(visited[V]) return;
		visited[V] = true;
		for(int i : A[V]) {
			if(!visited[i]) {
				DFS(i);
			}
		}
	}
	public static void BFS(int V) {
		Queue<Integer> queue = new LinkedList<Integer>();
		if(visited[V]) return;
		queue.add(V);
		visited[V] = true;
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			System.out.println(now + " ");
			for(int i : A[V]) {
				if(!visited[i]) {
					queue.add(i);
				}
			}
		}
	}

}

문제

예제를 실행했을때, 무한루프에 빠졌다.

원인

BFS메서드에서 while문으로 큐가 빌때까지 반복하는데, 인접리스트를 체크해서 방문하지 않았으면 큐에 넣는 작업을 하고, 방문배열에 true로 수정하는 코드가 빠졌다!

해결

BFS - while - for - if 문에서 방문하지않은경우, 큐에 추가하고나서 방문배열체크하도록 수정했다.
visited[i] = true; 추가!

Troubleshooting 2

문제

출력이 예제와 다르게 나와서 틀렸다.

원인

BFS,DFS에서 출력할 때 습관처럼 System.out.println()을 써서 하나 출력할때마다 줄바뀜이 됐다.
습관처럼 짜기보다, 예제에서 형식을 잘 파악해야할것같다.(인덱스사용 1부터 하는거나, 출력형태라든가...)

해결

DFS, BFS안에서 출력할때에는 System.out.print()써서 줄바꿈하지않도록 했고, DFS 호출이 끝나면 줄을 바꾸도록 main에 System.out.println()추가.

Troubleshooting3

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
static boolean[] visited;
static ArrayList<Integer>[] A;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		visited = new boolean[N+1];
		A = new ArrayList[N+1];
		for(int i=1; i<N+1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			A[start].add(end);
			A[end].add(start);
		}
		DFS(V);
		System.out.println();
		for(int i=1; i<N+1; i++) {
			visited[i] = false;
		}
		BFS(V);
		System.out.println();
	}
	
	public static void DFS(int V) {
		System.out.print(V + " ");
		if(visited[V]) return;
		visited[V] = true;
		for(int i : A[V]) {
			if(!visited[i]) {
				DFS(i);
			}
		}
	}
	public static void BFS(int V) {
		Queue<Integer> queue = new LinkedList<Integer>();
		if(visited[V]) return;
		queue.add(V);
		visited[V] = true;
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			System.out.print(now + " ");
			for(int i : A[V]) {
				if(!visited[i]) {
					queue.add(i);
					visited[i] = true;
				}
			}
		}
	}
}

문제

틀렸다.

원인

방문할 수 있는 노드가 여러개일경우, 노드 번호가 작은 것을 먼저 방문한다고 문제에 써있다.
이는 인접 노드를 오름차순으로 정렬한 후 진행해야하는데, 정렬하지않고 호출했다!

해결

main 메서드에서 Collection.sort()를 사용하여 정렬했다.

Troubleshooting 4

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
static boolean[] visited;
static ArrayList<Integer>[] A;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		visited = new boolean[N+1];
		A = new ArrayList[N+1];
		for(int i=1; i<N+1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			A[start].add(end);
			A[end].add(start);
		}
		
		for(int i=1; i<N+1; i++) {
			Collections.sort(A[i]);
		}
		
		DFS(V);
		System.out.println();
		for(int i=1; i<N+1; i++) {
			visited[i] = false;
		}
		BFS(V);
		System.out.println();
	}
	
	public static void DFS(int V) {
		System.out.print(V + " ");
		if(visited[V]) return;
		visited[V] = true;
		for(int i : A[V]) {
			if(!visited[i]) {
				DFS(i);
			}
		}
	}
	public static void BFS(int V) {
		Queue<Integer> queue = new LinkedList<Integer>();
		if(visited[V]) return;
		queue.add(V);
		visited[V] = true;
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			System.out.print(now + " ");
			for(int i : A[V]) {
				if(!visited[i]) {
					queue.add(i);
					visited[i] = true;
				}
			}
		}
	}
}

문제

틀렸다.

두번째 예제 입력시, 마지막 출력이 덜되는것을 볼 수 있다.

원인

BFS에서 큐가 빌때까지 while문을 돈다. 이때 가장 앞의 원소를 꺼내기위해 int now = queue.poll()을 하는데, while안에서의 for를 돌기위해서는 i : A[V]가 아니라, i : A[now]여야한다. 즉, 인접노드를 확인하기위해서, 현재 노드를 A의 파라미터로 넣어야한다.

해결

i : A[V] -> i : A[now]로 수정

제출코드

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

public class Main {
static boolean[] visited;
static ArrayList<Integer>[] A;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		visited = new boolean[N+1];
		A = new ArrayList[N+1];
		for(int i=1; i<N+1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			A[start].add(end);
			A[end].add(start);
		}
		
		for(int i=1; i<N+1; i++) {
			Collections.sort(A[i]);
		}
		
		DFS(V);
		System.out.println();
		visited = new boolean[N+1];
		BFS(V);
		System.out.println();
	}
	
	public static void DFS(int V) {
		System.out.print(V + " ");
		visited[V] = true;
		for(int i : A[V]) {
			if(!visited[i]) {
				DFS(i);
			}
		}
	}
	public static void BFS(int V) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(V);
		visited[V] = true;
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			System.out.print(now + " ");
			for(int i : A[now]) {
				if(!visited[i]) {
					queue.add(i);
					visited[i] = true;
				}
			}
		}
	}
}

헤맸던 부분

출력을 어떤 방식으로 하지?
-> 너무 복잡하게 생각했다. 처음에 BufferedWriter를 이용해서 쌓아둔 후 출력하려했는데, main에서 선언하니 DFS,BFS 메서드에서 사용시 선언되어있지않다는 에러가 떴다.
StringBuilder도 마찬가지...
-> 해결 : 답을 봤는데, 그때그때 출력하므로 DFS, BFS를 각각 호출할 때 바로 출력해주면된다. System.out.print() 사용
백준 11724를 풀때, DFS 메서드 초반에 if(visited[]) return을 써서, 방문했으면 이후를 진행하지않고, 끝낼 수 있게 했었다.
이를 로직처럼 기억하고, 여기에서도 처음에는 그렇게 작성했는데 답은 그런 코드가 없었다.
알고보니, 그때는 시작 노드를 입력받지않아서 main메서드에서 1부터 반복문 돌며 DFS를 실행했기때문에 그런 조건문으로 처리해줬던거고, 여기서는 시작노드가 정해지기때문에 DFS안에서 처음에 바로 방문했는지 체크할 필요는 없다!
(인접리스트의 원소를 체크하기위해 반복문 돌며 방문하지않았으면 DFS(재귀함수) 구현하는것과 다른이야기)

공부한 사항

Java에서 Queue 사용법 : LinkedList 이용
-> Queue<Integer> queue = new LinkedList<Integer>()
BFS : 너비 우선 탐색 : 시작노드에서 가까운 것부터 탐색
BFS 구현 : 재귀함수 x, 큐 이용 -> 재귀함수 대신 반복문(큐가 빌때까지 반복)이용
ArrayList 정렬 (배열과 다름!)
-> 오름차순 정렬 : Collections.sort(list)
-> 내림차순 정렬 : Collections.sort(list, Collections.reverseOrder());
visited[] 사용 후 재사용위해 초기화
-> 반복문 돌며 원소 하나하나 지정할 필요 없다.
-> 처음에 초기화 했듯이 visited = new boolean[N+1];로 초기화하면된다!

Benjamin

이전 포스트

[백준] 2023 : 신기한 소수 - JAVA

다음 포스트