[백준][Java] 1260번 : DFS와 BFS

2024. 8. 20. 00:16·PS/백준

[문제 링크]

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


문제 설명

  • 그래프를 DFS, BFS로 탐색한 결과 출력
  • 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
  • 더 이상 방문할 수 있는 점이 없는 경우 종료
  • 입력: 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V, 간선이 연결하는 두 정점의 번호
  • 출력: DFS 수행결과, BFS 수행 결과

 

 

 

문제 풀이

  • DFS는 재귀를 사용해서 구현
  • BFS는 큐를 사용해서 구현

(1) Array 2차원 배열 사용

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

public class Main {
    public static int n, m, v;
    public static boolean[] visited;   //방문 처리 배열
    public static int[][] graph;	//Array 2차원 배열 사용
    public static Queue<Integer> q = new LinkedList<>();

    public static void dfs(int v) {
        visited[v] = true;  //현재 정점 방문 처리
        System.out.print(v + " ");

        for (int i = 1; i <= n; i++) {
            if (graph[v][i] == 1 && !visited[i]) {  //방문하지 않은 노드일 경우
                dfs(i);
            }
        }
    }

    public static void bfs(int v) {
        visited[v] = true;  //현재 정점 방문 처리
        q.offer(v);

        //큐가 빌 때까지 실행
        while (!q.isEmpty()) {
            int x = q.poll();
            System.out.print(x + " ");

            for (int i = 1; i <= n; i++) {
                if (graph[x][i] == 1 && !visited[i]) {  //방문하지 않은 노드일 경우
                    q.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

     public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

         StringTokenizer st = new StringTokenizer(br.readLine());
         n = Integer.parseInt(st.nextToken());  //정점의 개수
         m = Integer.parseInt(st.nextToken());  //간선의 개수
         v = Integer.parseInt(st.nextToken());  //탐색 시작 번호

         graph = new int[n+1][n+1];
         for (int i = 0; i < m; i++) {
             StringTokenizer st1 = new StringTokenizer(br.readLine());
             int x = Integer.parseInt(st1.nextToken());
             int y = Integer.parseInt(st1.nextToken());
             graph[x][y] = graph[y][x] = 1; //양방향
         }

         visited = new boolean[n + 1];
         dfs(v);
         System.out.println();
         visited = new boolean[n + 1];
         bfs(v);
    }
}

 

 

 

(2) ArrayList 2차원 배열 사용

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

public class Main {
    public static int n, m, v;
    public static boolean[] visited;
    public static ArrayList<Integer>[] graph;   //ArrayList 2차원 배열 사용
    public static Queue<Integer> q = new LinkedList<>();

    public static void dfs(int v) {
        visited[v] = true;  //현재 정점 방문 처리
        System.out.print(v + " ");

        for (Integer i : graph[v]) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

    public static void bfs(int v) {
        visited[v] = true;  //현재 정점 방문 처리
        q.offer(v);

        //큐가 빌 때까지 실행
        while (!q.isEmpty()) {
            int x = q.poll();
            System.out.print(x + " ");


            for (Integer i : graph[x]) {
                if (!visited[i]) {  //방문하지 않은 노드일 경우
                    q.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

     public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

         StringTokenizer st = new StringTokenizer(br.readLine());
         n = Integer.parseInt(st.nextToken());  //정점의 개수
         m = Integer.parseInt(st.nextToken());  //간선의 개수
         v = Integer.parseInt(st.nextToken());  //탐색 시작 번호

         graph = new ArrayList[n + 1];

         for (int i = 0; i <= n; i++) {
             graph[i] = new ArrayList<>();
         }

         for (int i = 0; i < m; i++) {
             StringTokenizer st1 = new StringTokenizer(br.readLine());
             int x = Integer.parseInt(st1.nextToken());
             int y = Integer.parseInt(st1.nextToken());
             graph[x].add(y);
             graph[y].add(x); //양방향
         }

         //방문가능한 정점이 여러개일 경우, 번호가 작은 것부터 먼저 방문하기 위해 오름차순 정렬
         for (ArrayList<Integer> list : graph) {
             Collections.sort(list);
         }

         visited = new boolean[n + 1];
         dfs(v);
         System.out.println();
         visited = new boolean[n + 1];
         bfs(v);
    }
}
저작자표시 비영리 변경금지 (새창열림)

'PS > 백준' 카테고리의 다른 글

[백준][Java] 18870번 : 좌표 압축  (2) 2024.09.17
[백준][Java] 11720번 : 숫자의 합  (0) 2024.08.20
[백준][Java] 10951번 : A + B - 4 - EOF  (1) 2024.06.26
[백준][Java] 27866번 : 문자와 문자열  (1) 2024.06.26
[백준][Java] 11382번 : 꼬마 정민  (0) 2024.04.17
'PS/백준' 카테고리의 다른 글
  • [백준][Java] 18870번 : 좌표 압축
  • [백준][Java] 11720번 : 숫자의 합
  • [백준][Java] 10951번 : A + B - 4 - EOF
  • [백준][Java] 27866번 : 문자와 문자열
nyrimmm
nyrimmm
  • nyrimmm
    개발기록
    nyrimmm
  • 전체
    오늘
    어제
  • 글쓰기 관리
    • 분류 전체보기 (85)
      • Java (6)
      • Spring & SpringBoot (3)
      • Network (1)
      • DataBase (0)
      • SQL (1)
      • IntelliJ (3)
      • Git (0)
      • 자료구조 & 알고리즘 (2)
      • 트러블 슈팅 (1)
        • Spring (1)
      • PS (67)
        • 백준 (24)
        • 프로그래머스 (0)
        • SQL (10)
        • 이코테 (33)
      • 후기 & 회고 (1)
  • 태그

  • 인기 글

  • 최근 글

  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
nyrimmm
[백준][Java] 1260번 : DFS와 BFS
상단으로

티스토리툴바