BOJ 1260 - DFS와 BFS

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

1260번: DFS와 BFS

 

난이도 : 실버 2

 

※ 풀이방법

 

1. 인접 행렬

 

2. 인접 리스트

 

 

 

---

1. 인접 행렬

 

 

static Integer N, M, V;
static int[][] adj; //인접 행렬
static boolean[] visit; // 방문 여부

N : 정점의 개수

M : 간선의 개수

V : 탐색을 시작할 정점 번호

 

 

static void input() throws IOException {
    N = scan.nextInt();
    M = scan.nextInt();
    V = scan.nextInt();
    adj = new int[N + 1][N + 1];
    for (int i = 1; i <= M; i++) {
        Integer x = scan.nextInt();
        Integer y = scan.nextInt();
        adj[x][y] = 1;
        adj[y][x] = 1;
    }
}

 

 

사용자 입력

 

 

static void dfs(Integer x) {
    visit[x] = true;
    sb.append(x).append(' ');

    for (int y = 1; y <= N; y++) {
        if (adj[x][y] == 0) {
            continue;
        }
        if (visit[y] == true) {
            continue;
        }
        dfs(y);
    }
}

★ DFS : Recursive를 이용해 구현

 

 

 

 

 

static void bfs(Integer x) {
    Queue<Integer> que = new LinkedList<>();

    que.add(x);
    visit[x] = true;

    while (!que.isEmpty()) {
        x = que.poll();
        sb.append(x).append(' ');
        for (int y = 1; y <= N; y++) {
            if (adj[x][y] == 0) {
                continue;
            }
            if (visit[y] == true) {
                continue;
            }
            que.add(y);
            visit[y] = true;
        }
    }
}

★ BFS : Queue를 이용해 구현

 

 

 

 

static void pro() {
    visit = new boolean[N + 1];
    dfs(V);
    sb.append("\n");
    for (int i = 1; i <= N; i++) {
        visit[i] = false;
    }
    bfs(V);
    System.out.println(sb);
}

process() : 앞에서 선언한 dfs(), bfs() 실행

 

 

 

 

public static void main(String[] args) throws IOException {
    input();
    pro();
}

main() 메서드