[자바] 백준 24479번: 알고리즘 수업 - 깊이 우선 탐색 1

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

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

 

---

인접행렬로 코드를 작성했다가 메모리초과가 났다.

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

public class P24479 {
	static count=0;
	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 r = Integer.parseInt(st.nextToken());

		int[][] arr = new int[n+1][n+1];
		int [] visited=new int[n+1];
		for(int i=0;i<n+1;i++) {
			visited[i]=0;
		}
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			arr[u][v]=arr[v][u]=1;
		}
		
		dfs(r,n,arr,visited);
		for(int i=1;i<=n;i++) {
			System.out.println(visited[i]);
		}
		
	}
	
	static void dfs(int r,int n,int[][] arr,int[] visited) {
		visited[r]=++count;
		
		for(int i=1;i<=n;i++) {
			if(visited[i]==0&&arr[r][i]==1) {
				
				dfs(i,n,arr,visited);
			}
			
		}
		
	}

}

그래서 인접리스트 방식으로 다시 작성하기로 했다.

 

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

public class P24479 {

	static int count=0;
	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 r = Integer.parseInt(st.nextToken());

		LinkedList[] list = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			list[i] = new LinkedList<Integer>();
		}

		int[] visited = new int[n + 1];
		for (int i = 0; i < n + 1; i++) {
			visited[i] = 0;
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			list[u].add(v);
			list[v].add(u);
		}

		for (int i = 1; i <= n; i++) {
			Collections.sort(list[i]);
		}

		dfs(r, visited, list);
		
		for(int i=1;i<=n;i++) {
			System.out.println(visited[i]);
		}

	}

	static void dfs(int r, int[] visited, LinkedList[] list) {
		visited[r]=++count;

		Iterator<Integer> it = list[r].iterator();
		while (it.hasNext()) {
			int next = it.next();

			if (visited[next] == 0) {
				
				dfs(next,visited,list);
			}
		}
	}

}

연결리스트 배열을 만들어서 사용했고

연결리스트는 iterator 이용하여 순회하였다.