[백준 11724 - 연결 요소의 개수] DFS를 활용한 문제 풀기

2024. 2. 24. 01:05·문제 풀이/백준 문제풀이
728x90
반응형
SMALL

 

위 문제는 DFS풀이의 가장  기본적인 문제이다.

 

문제를 풀기에 앞서 풀이 순서를 짚어보자.

1. 최대 정점의 개수와 문제풀이 시간을 대조해본다.
   -  문제 풀이 시간은 3초이다. 최대 노드의 개수는 1000개로 n^2의 복잡도로 문제를 풀어도 충분히 시간이 남는다.

2. 해당 그래프를 직접 그려본다.

    - 첫 예시의 그래프를 만들어보자면 다음과 같다. (혼을 담아 정성스럽게 그려보았다)

3. 이처럼 두개의 그래프가 그려지는것을 확인할 수 있다. 이를 코드로 작성하기 위한 슈도코드를 작성해본다.

n(노드 개수) , m(엣지 개수)

A(그래프 데이터 저장 인접 리스트)

visited(방문 기록 저장 배열)

for(n만큼 반복
{A 인접 리스트의 각 ArrayList초기화}

for(m의 개수만큼 반복하기)
{ A인접 리스트에 그래프 데이터 저장하기 }

for(n의 개수만큼 반복하기)
{ if(방문하지 않은 노드가 있으면){ 연결 요소 개수 ++ DFS 실행하기 }

//DFS구현하기
{
DFS{ if(현재 노드 == 방문노드) return;
visited 배열에 현재 노드 방문 기록하기
현재 노드의 연결 노드 중 방문하지 않는 노드로 DFS 실행하기(재귀 함수 형태)
}

 

4.이를 토대로 재귀함수를 사용한 스택형식의 DFS를 구현한다.

public class test {
    //방문 배열
    static boolean[] visited;
    //인접 리스트
    static ArrayList<Integer>[] A;
    
    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());
       
        visited = new boolean[n+1];
        A = new ArrayList[n + 1];
        for (int i = 1; i < n + 1; i++) {
            //인접리스트배열 초기화
            A[i] = new ArrayList<Integer>();
        }
        //인접 리스트에 그래프 데이터 저장
        for (int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
        }
        //개수를 판단할 count변수
        int count =0;

        //방문배열에 등록되지 않은 노드를 재귀함수를 통해 찾아냄
        for (int i = 1; i <n+1; i++) {
            if(!visited[i]) {
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
      
    }

    private static void DFS(int v) {
        if(visited[v]){
            return;
        }
        visited[v] = true;

        for (int i : A[v]) {
            if (!visited[i]) {
                
                DFS(i);
            }
        }
    }
}
728x90
반응형
SMALL

'문제 풀이 > 백준 문제풀이' 카테고리의 다른 글

[백준 - 2178/ 자바(Java)] 미로 탐색 문제 BFS로 해결하기  (1) 2024.02.28
[백준 -24480 ] java , 알고리즘 수업 - 깊이 우선 탐색 2  (2) 2024.02.26
숫자만 추출하기  (1) 2023.12.10
팰린드롬(회문 문자열)  (0) 2023.12.10
회문문자열  (0) 2023.12.10
'문제 풀이/백준 문제풀이' 카테고리의 다른 글
  • [백준 - 2178/ 자바(Java)] 미로 탐색 문제 BFS로 해결하기
  • [백준 -24480 ] java , 알고리즘 수업 - 깊이 우선 탐색 2
  • 숫자만 추출하기
  • 팰린드롬(회문 문자열)
공부하고 기억하는 공간
공부하고 기억하는 공간
IT 비전공자로 시작하여 훌륭한 개발자가 되기 위해 공부하고 있는 공간입니다. 틀린 내용이나 부족한 부분이 있으면 댓글로 알려주세요 바로 수정하겠습니다.
IT - railroadIT 비전공자로 시작하여 훌륭한 개발자가 되기 위해 공부하고 있는 공간입니다. 틀린 내용이나 부족한 부분이 있으면 댓글로 알려주세요 바로 수정하겠습니다.
    250x250
  • 공부하고 기억하는 공간
    IT - railroad
    공부하고 기억하는 공간
  • 전체
    오늘
    어제
    • 분류 전체보기 (325)
      • 면접 준비 (22)
        • OS (6)
        • Spring Security (0)
        • Java (3)
        • DB (11)
        • Network (3)
      • ElasticSearch (2)
      • Kafka (4)
      • Spring (22)
        • Spring Cloud (7)
        • Security6 (5)
        • JPA (12)
        • 프로젝트 리팩토링 회고록 (4)
        • Logging (8)
        • Batch (2)
      • Redis (17)
        • Redis 개념 (8)
        • Redis 채팅 (5)
        • Redis 읽기쓰기 전략 (1)
      • AWS (11)
      • 리눅스 (29)
        • 리눅스 마스터 2급 (5)
        • 네트워크(기초) (7)
        • 리눅스의 이해 (6)
        • 리눅스의 설치 (2)
        • 리눅스 운영 및 관리 (6)
      • JAVA-기초 (16)
        • JAVA기본 (11)
        • Design Pattern (5)
      • JSP (27)
        • JSP 기본 개념 (10)
        • JSP (1)
      • SQL (1)
      • TIL (36)
      • 문제 풀이 (2)
        • Programmers (9)
        • 백준 문제풀이 (28)
      • JavaScript (10)
      • HTML (17)
      • Ngrinder (1)
        • Ngrinder 문서 정리 (1)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      스프링프레임워크
      redis
      spring redis
      springsecurity
      백준
      자바 알고리즘
      Springframework
      자바기초
      리눅스마스터2급
      Spring
      redis 채팅
      HTML
      자바 면접질문
      Til
      jsp request
      자바스크립트
      java
      리눅스마스터2급정리
      jsp기초
      자바 면접
      리눅스
      JS
      CSS
      레디스
      JSP
      Spring Data Redis
      자바
      프로그래머스
      자바 반복문
      JavaScript
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    공부하고 기억하는 공간
    [백준 11724 - 연결 요소의 개수] DFS를 활용한 문제 풀기

    개인정보

    • 티스토리 홈
    • 포럼
    • 로그인
    상단으로

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.