백준 24479,24480 알고리즘 수업 - 깊이 우선 탐색 1,2 / JAVA

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

처음에 문제 이해가 안되서 다른사람풀이 참고하며 한참 해맸던 문제였다.

 

문제분석

예제 입력을 노드와 그래프로 나타내면 아래와 같다

5개의 노드지만 이동하는 간선이 없으므로 생략한다.

 

출력은 각 노드로 이동하는 우선순위를 구하라는 것이다 < 이 부분 아직도 문제읽으면 모르겠음..

문제에서 각 정점을 오름차순으로 방문하라 했으니 방문순서는 1 -> 2 -> 3 -> 4 -> 5 로 우선순위를 출력해주면된다.

1번 노드는 1번에서 출발하므로 -> 1

2번 노드는 1번 노드에 연결된 2,4 노드 중 하나로 2번째로 방문 -> 2

3번 노드는 1번에서 2번으로 이동 후 2번노드에연결된 1,3,4 중 하나로 3번째로 방문 -> 3

4번 노드는 1번에서 2번에서 3번으로 이동 후 3번노드에 연결된 2,4 중 하나로 4번째로 방문 -> 4

5번 노드는 1번에서 갈 수 없으므로 문제에 제시된것처럼 -> 0

 

* 예제입력된 대로 ArrayList를 구성할 경우

1 : {4,2}

2 : {1,3,4}

3 : {2,4}

4 : {1,2,3} 이 되어 1번 노드에서 4번을 먼저 탐색하게 되므로 오름차순 정렬인 Collections.sort 를 우선 수행해줘야한다

 

public class boj_24479 {
	static ArrayList<Integer>[] arr;
	static boolean[] visited;
	static int[] answer;
	static int cnt = 1;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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 r = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[n+1];
		visited = new boolean[n+1];
		answer = new int[n+1];
		//그래프초기화
		for(int i = 0; i<=n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		//list에 저장
		for(int j = 0; j < m; j++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		
		//오름차순 정렬
		for(int k = 1; k <= n; k++) {
			Collections.sort(arr[k]);
		}
		visited[r] = true;
		dfs(r);
		
		for(int l = 1; l <= n; l++) {
			System.out.println(answer[l]);
		}
	}
	
	public static void dfs(int node) {
		answer[node] = cnt;
		for(int x : arr[node]) {
			if(visited[x] == false) {
				visited[x] = true;
				cnt++;
				dfs(x);
			}
		}
	}
}

 

 

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

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

이 문제는 위 24479 문제와 동일한 유형으로 다른점은 오름차순이 아닌 내림차순을 명시한 것이다.

내림차순 구현은 Collections.sort(배열, Collections.reverseOrder()) 를 사용하였다. 기회가 될때 Compare 이용 분석을 더 해보자

public class boj_24480 {
	
	static ArrayList<Integer>[] arr;
	static boolean[] visited;
	static int[] answer;
	static int cnt = 1;

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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 r = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[n+1];
		visited = new boolean[n+1];
		answer = new int[n+1];
		
		// 그래프초기화
		for(int i = 0; i <= n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		//그래프 그리기
		for(int j = 0; j < m; j++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		
		// 내림차순정렬
		for(int k = 1; k <= n; k++) {
			Collections.sort(arr[k], Collections.reverseOrder());
		}
		
		visited[r] = true;
		dfs(r);
		for(int l = 1; l <= n; l++) {
			System.out.println(answer[l]);
		}
	}
	
	public static void dfs(int node) {
		answer[node] = cnt;
		if(arr[node] == null) {
			return;
		} else {
			for(int x : arr[node]) {
				if(visited[x] == false) {
					visited[x] = true;
					cnt++;
					dfs(x);
				}
			}
		}

	}
}

24480은 계속 풀리지 않아 오픈채팅에 문의도 해봤으나... 결국 오타문제였다..ㅠㅠ;;