[백준] 1260번 - DFS와 BFS (Java)(○)

 

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

1260번: DFS와 BFS

 

<문제 분석>

1. 무방향 그래프이다.

2. 방문할 정점이 여러개이면 작은 번호부터 방문하다.

 

<문제 풀이 #1>

* DFS

1. 무방향 그래프를 표현하기 위해 vertex 배열을 사용한다.

2. DFS() 파라미터는 다음 방문할 정점 번호를 넘긴다.

3. DFS() 내부에서 for문으로 다음 방문 정점으로 확산한다.

4. 방문배열을 사용해서 방문할 정점은 스킵한다.

5. 간선이 아니면 (값이 0) 스킵한다.

 

* BFS

1. DFS와 기본 형태는 비슷하다 큐를 사용한다.

2. DFS와 다르게 확산처리를 while문 안에서 하기에 방문처리도 그 안에서 해준다.

 

 

<코드 구현 #1 - 인접행렬>

import java.util.*;

/*
백준 1260번 : DFS와 BFS
*/

public class Main {

    int N;
    int M;
    int V;
    int A[][];
    boolean visited[];
    
	void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        V = in.nextInt();

        // 무방향 그래프를 표현하기 위해 vertex 배열 사용
        A = new int[N+1][N+1];
        for (int i=0; i<M; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            A[s][e] = 1;//양방향 모두 값 삽입
            A[e][s] = 1;
        }
	}

    void DFS(int v) {
        visited[v] = true;
        System.out.print(v+" ");
        for (int i=1; i<=N; i++) {
            if (visited[i]) continue;//방문한 정점이면 스킵
            if (A[v][i] == 0) continue;//값이 0이면 간선이 없으므로 스킵
            DFS(i);
        }
    }

    void BFS(int v) {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(v);
        visited[v] = true;

        while (!Q.isEmpty()) {
            v = Q.poll();
            System.out.print(v+" ");
            for (int i=1; i<=N; i++) {
                if (visited[i]) continue;//방문한 정점이면 스킵
                if (A[v][i] == 0) continue;//값이 0이면 간선이 없으므로 스킵
                Q.offer(i);
                visited[i] = true;//확산한 정점을 방문처리
            }
        }
    }

    void Solve() {
        visited = new boolean[N+1];
        DFS(V);
        System.out.println();

        visited = new boolean[N+1];
        BFS(V);
        System.out.println();
    }
	public static void main(String[] args) {
		Main m = new Main();
		m.InputData();
        m.Solve();
	}
}

---

<풀이 #2>

1. 메모리 사용량과 실행 시간을 줄이기 위해 다음과 같이 변경해 보았다.

  - 인접행렬 방식 -> 인접리스트 방식

  - 노드 방문 시 마다 System.out.print()를 호출하는 것을 StringBuilder로 머지해서 마지막 한번만 출력하는 방식

2. 문제에서 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문" 하라는 구문이 있는데 인접리스트에서 이것을 어떻게 구현할 수 있을지 고민을 많이 했다. 결국 혼자서 정확한 코드를 생각해 내지는 못하고 다른 코드를 참고했다.

        // 방문번호 기준으로 오름차순 정렬하기(인접리스트는 필요함)
        for (int i=1; i<=N; i++) {
            Collections.sort(list.get(i));
        }

 

<구현 #2 - 인접리스트>

import java.io.*;
import java.util.*;

public class Main {
	int N, M, V;
    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    static boolean visited[];
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    
    void DFS(int v) {
        visited[v] = true;
        sb.append(v).append(' ');
        // 재귀호출 조건
        for (int x : list.get(v)) {
            if (visited[x]) continue;
            DFS(x);
        }
    }

    void BFS(int v) {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(v);
        visited[v] = true;
        sb.append(v).append(' ');
        while (!Q.isEmpty()) {
            int now = Q.poll();
            for (int x : list.get(now)) {
                if (visited[x]) continue;
                visited[x] = true;
                Q.offer(x);
                sb.append(x).append(' ');
            }
        }
    }

    void Solve() {
        // 방문번호 기준으로 오름차순 정렬하기(인접리스트는 필요함)
        for (int i=1; i<=N; i++) {
            Collections.sort(list.get(i));
        }

        // DFS 호출
        visited = new boolean[N+1];
        DFS(V);
        sb.append('\n');

        // BFS 호출
        visited = new boolean[N+1];
        BFS(V);
        sb.append('\n');
        System.out.println(sb.toString());
    }

	void InputData() throws IOException{
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str," ");
		N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
		for (int i=0; i<N+1; i++) {
            list.add(new ArrayList<>());
        }
		for (int i=0; i<M; i++){
			str = br.readLine();
            st = new StringTokenizer(str," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
		}
		br.close();
	}

	public static void main(String[] args) throws IOException {
		Main m = new Main();
		m.InputData();//입력
		m.Solve();//여기서부터 작성
	}
}

 

 

메모리 사용량은 반으로 줄었고, 실행시간도 1/3 수준으로 개선 되었다.