백준 24479 & 24480 알고리즘 수업 - 깊이 우선 탐색 1&2(DFS)

문제, 입출력, 테스트케이스

 

문제, 입출력, 테스트케이스

이번에는 두 문제를 갖고와봤다. 백준 단계별로 풀어보기 1, 2번 문젠데 그냥 dfs를 오름차순, 내림차순으로 하느냐의 차이여서 java에서 오름, 내림차순 정렬하는 법만 알면 되니 한 큐에 풀어제꼈다

 

<문졔 접근/풀이과정>
1. DFS로 풀어야한다.
2. 정점의 수가 100,000개까지이므로  100,000 x 100,000이므로 2차원 배열로는 안된다.
3. 리스트나 우선순위큐를 이용하여 풀어야 한다.
4. 리스트를 사용할 경우 정렬 함수를 써야하며 우선순위큐를 사용할 경우 오름차순인지 내림차순인지 정의해줘야 한다. -> 본인은 리스트 + 정렬 함수를 썼다.

정렬과 관련해서는 이전에 작성한 글을 참고하면 좋을 듯 하다.

2022.02.20 - [프로그래밍공부(ProgrammingStudy)/자바(JAVA)] - (JAVA/자바)compareTo와 Comparator 그리고 정렬

(JAVA/자바)compareTo와 Comparator 그리고 정렬

<24479번 소스코드 - 오름차순 DFS>

package boj;

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

public class Boj_24479 {
	static int N, M, R, answer[], cnt;
	static List<List<Integer>> arr;
	static boolean visited[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stz.nextToken());
		M = Integer.parseInt(stz.nextToken());
		R = Integer.parseInt(stz.nextToken());
		visited = new boolean[N+1];
		answer = new int[N+1];
		cnt = 1;
		arr = new ArrayList<>();
		for (int i = 0; i <= N ; i++) { // 정점 초기화 
			arr.add(new ArrayList<>()); // 정점에 리스트 넣기
		}
		
		for (int i = 0; i < M; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			
			arr.get(from).add(to);
			arr.get(to).add(from);
		}
		
		for (int i = 1; i <= N; i++) {
			Collections.sort(arr.get(i));
		}
		answer[R] = cnt++;
		visited[R] = true;
		
		dfs(R);
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= N; i++) {
			sb.append(answer[i]).append("\n");
		}
		sb.setLength(sb.length()-1);
		System.out.print(sb.toString());
		
		
	}
	private static void dfs(int node) {
		
		List<Integer> temp = arr.get(node);
		int size = temp.size();
		for (int i = 0; i < size; i++) {
			int nextNode = temp.get(i);
			if(visited[nextNode]) continue;
			answer[nextNode] = cnt++;
			visited[nextNode] = true;
			dfs(nextNode);
		}
	}
}

<24479번 소스코드 - 내림차순 DFS>

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Boj_24480 {
	static int N, M, R, answer[], cnt;
	static List<List<Integer>> arr;
	static boolean visited[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stz.nextToken());
		M = Integer.parseInt(stz.nextToken());
		R = Integer.parseInt(stz.nextToken());
		visited = new boolean[N+1];
		answer = new int[N+1];
		cnt = 1;
		arr = new ArrayList<>();
		for (int i = 0; i <= N ; i++) { // 정점 초기화 
			arr.add(new ArrayList<>()); // 정점에 리스트 넣기
		}
		
		for (int i = 0; i < M; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			
			arr.get(from).add(to);
			arr.get(to).add(from);
		}
		
		for (int i = 1; i <= N; i++) {
			Collections.sort(arr.get(i), new Comparator<Integer>() {

				@Override
				public int compare(Integer o1, Integer o2) {
					// TODO Auto-generated method stub
					return o2 - o1;
				}
			});
		}
		answer[R] = cnt++;
		visited[R] = true;
		
		dfs(R);
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= N; i++) {
			sb.append(answer[i]).append("\n");
		}
		sb.setLength(sb.length()-1);
		System.out.print(sb.toString());

		
	}
	private static void dfs(int node) {
		
		List<Integer> temp = arr.get(node);
		int size = temp.size();
		for (int i = 0; i < size; i++) {
			int nextNode = temp.get(i);
			if(visited[nextNode]) continue;
			answer[nextNode] = cnt++;
			visited[nextNode] = true;
			dfs(nextNode);
		}
	}
}