b24497. 알고리즘 수업 - 깊이 우선 탐색 1

2025. 1. 27. 23:59·Algorithm & Data Structures/BOJ

 

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

 

 

 

이 문제는 그래프 탐색 알고리즘인 DFS(Depth First Search)를 활용하여

특정 시작 정점에서 탐색을 수행하며, 각 정점을 방문한 순서를 기록하는 문제다.

아래 코드는 문제를 해결하기 위한 전체적인 흐름과 구현 방식을 포함하고 있다.
우선, 입력으로는 정점의 개수 N, 간선의 개수 M, 탐색 시작 정점 R이 주어진다.

이 정보를 기반으로 그래프를 인접 리스트 형태로 표현하기 위해 list라는 배열을 생성한다.

이 배열은 각 정점이 연결된 다른 정점들을 저장하는 리스트를 담고 있다.

이를 통해 그래프를 효율적으로 관리하고 탐색을 수행할 수 있다.

입력으로 주어진 간선을 처리하여 무방향 그래프를 구성한다.

각 정점의 연결 정보를 정렬하여 탐색 시 오름차순으로 방문할 수 있도록 준비한다.

이렇게 정렬된 그래프는 문제의 조건을 만족하기 위해 필요하다.

깊이 우선 탐색(DFS)을 수행하기 위해 재귀 함수 DFS를 작성한다.

이 함수는 탐색을 시작하는 정점을 입력받아,

방문 순서를 기록하는 배열 ans에 현재 카운트를 저장한다.

이후 해당 정점에 연결된 모든 정점을 탐색하며,

아직 방문하지 않은 정점에 대해 재귀적으로 DFS를 호출한다.

방문 순서는 count라는 전역 변수로 관리하여, 탐색 순서를 차례로 기록된다.

마지막으로, 각 정점의 방문 순서를 출력한다.

 

 

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

public class b24479 {

    static int N, M, R;
    static int[] ans;
    static ArrayList<Integer>[] list;
    static int count;

    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());
        R = Integer.parseInt(st.nextToken());

        list = new ArrayList[N + 1];
        ans = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

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

        count = 1; // 초기값 설정
        DFS(R);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(ans[i]).append("\n");
        }
        System.out.println(sb);
    }

    static void DFS(int r) {
        ans[r] = count++;
        for (int next : list[r]) {
            if (ans[next] == 0) { // 방문하지 않은 정점인 경우
                DFS(next);
            }
        }
    }
}

'Algorithm & Data Structures > BOJ' 카테고리의 다른 글

b.1725 히스토그램  (0) 2025.02.06
b.17299 오등큰수  (1) 2025.02.04
b.17298 오큰수  (1) 2025.01.23
b.2293 동전 1  (0) 2025.01.21
b2629. 양팔저울  (0) 2025.01.17
'Algorithm & Data Structures/BOJ' 카테고리의 다른 글
  • b.1725 히스토그램
  • b.17299 오등큰수
  • b.17298 오큰수
  • b.2293 동전 1
Geisha
Geisha
개발 일기
  • Geisha
    Geisha
    Geisha
  • 전체
    오늘
    어제
    • 분류 전체보기 (316)
      • Algorithm & Data Structures (238)
        • BOJ (96)
        • SWEA (1)
        • Programers (137)
        • Data Structures (3)
      • DB (25)
        • SQL (19)
        • RDBMS (2)
      • Java (1)
        • Class (1)
      • Spring (5)
        • Spring MVC (1)
        • Annotations (1)
      • CS (36)
        • 운영체제 (13)
        • 네트워크 (5)
      • Tool (6)
        • Git (5)
        • AWS (1)
      • Project (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    골드
    dp
    알고리즘
    Union-Find
    유니온파인드
    스택
    동적계획법
    binarySearch
    구현
    PriorityQueue
    투포인터
    다익스트라
    baekjoon
    DynamicProgramming
    Stack
    unionfind
    algorithm
    BFS
    백트래킹
    경로압축
    백준
    Java
    Dijkstra
    programmers
    전위순회
    프로그래머스
    이분탐색
    SQL
    dfs
    후위순회
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Geisha
b24497. 알고리즘 수업 - 깊이 우선 탐색 1
상단으로

티스토리툴바