[BOJ] 2644. 촌수계산

2024. 3. 5. 14:16· Algorithm/Java
목차
  1. 문제
  2. 입력 예제
  3. 문제 풀이
  4. BFS
  5. DFS

 

문제

 

 

 

입력 예제

 

 

 

 

 

문제 풀이

 

 

입력 예제를 바탕으로 그래프화 해본 결과, 최단 경로를 구하는 방식이나 깊이 우선 탐색을 이용하는 방법으로 풀이가 가능하다는 생각이 들었다. DFS & BFS 둘 다로 풀이할 수 있는 문제이므로 두 알고리즘을 각각 적용하여 풀이해보기로 했다.

 

 

 

BFS

 

 

위 그래프의 인접행렬과 노드 간 연결 관계(양방향)를 테이블로 표현해보았다.

추가) 아래 그림에서는 인접리스트라고 적었지만 구현은 인접행렬 방식으로 되어 있습니다.

 

인접행렬과 인접리스트의 차이가 궁금하다면 맨 아래 링크된 글을 참고 바랍니다.

 

 

 

 

방문 배열값 업데이트 과정은 다음과 같다.

 

 

 

import java.util.*;

public class BOJ2644 {

    static int n, m, start, end;
    static int[][] arr;
    static int[] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr = new int[n+1][n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());
        visited = new int[n+1];

        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 서로 양방향으로 연결되어 있음을 의미
            arr[x][y] = 1;
            arr[y][x] = 1;
        }

        BFS(start);

        System.out.println(visited[end] == 0 ? -1 : visited[end]);
    }

    public static void BFS(int index) {
        Queue<Integer> queue = new LinkedList<Integer>();

        // 시작점 큐에 삽입
        queue.add(index);

        System.out.println("start queue:" + queue.toString());

        while (!queue.isEmpty()) {
            int curr = queue.poll();

            if (curr == end) break;
            for (int i=1; i<=n; i++) {
                // 방문 조건 : 현재 노드와 다음 노드가 연결된 상태이고 아직 방문하지 않은 상태일 때
                if (arr[curr][i] == 1 && visited[i] == 0) {
                    queue.add(i);
                    // i번째 배열값에 1씩 +하며 카운트
                    visited[i] = visited[curr] + 1;
                }
            }
        }
    }
}

 

 

 

DFS

 

위 문제를 DFS 방식으로도 풀이해보았다. BFS와 전체적인 틀은 같으나 queue를 사용하는 대신 재귀적인 탐색을 통해 결과값을 출력하는 형태이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ2644_DFS {

    static int n, m, start, end, result = -1;
    static int[][] arr;
    static int[] visited;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());
        visited = new int[n + 1];

        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 서로 양방향으로 연결되어 있음을 의미
            arr[x][y] = arr[y][x] = 1;
        }

        DFS(start, 0);
        System.out.println(result);
    }

    public static void DFS(int index, int cnt) {

        if (index == end) {
            result = cnt;
            return;
        }

        for (int i=1; i<=n; i++) {

            // 방문조건: start와 연결되어 있으면서 아직 방문하지 않은 상태
            if (arr[index][i] == 1 && visited[i] == 0) {
                // 방문 횟수 카운트 1씩 증가
                visited[i] = visited[i] + 1;

				// 촌수 관계 증가시키면서 다음 촌수로 이동
                DFS(i, cnt+1);
            }
        }
    }
}

 

 

위 코드의 탐색 순서를 보면 다음과 같이 탐색되는 것을 확인할 수 있다.

 

 

 

 

 

 

https://loosie.tistory.com/151

 

[알고리즘/ 그래프] DFS와 BFS 정리 (Java)

깊이 우선 탐색 DFS 각 정점 노드를 깊게 탐색하는 방식으로 매 탐색을 stack으로 쌓으면서 갈 수 있는 최대한 깊이를 탐색하고 갈 곳이 없다면 이전 정점으로 돌아간다. 모든 정점을 발견하는 가

loosie.tistory.com

 

반응형

'Algorithm > Java' 카테고리의 다른 글

[BOJ] 2751. 수 정렬하기2  (0) 2024.09.12
[BOJ] 2606. 바이러스  (0) 2024.08.08
[BOJ] 1260. DFS와 BFS  (0) 2024.04.11
[BOJ] 13305. 주유소  (0) 2024.01.18
[BOJ] 2178. 미로탐색  (0) 2024.01.17
  1. 문제
  2. 입력 예제
  3. 문제 풀이
  4. BFS
  5. DFS
'Algorithm/Java' 카테고리의 다른 글
  • [BOJ] 2606. 바이러스
  • [BOJ] 1260. DFS와 BFS
  • [BOJ] 13305. 주유소
  • [BOJ] 2178. 미로탐색
빵판 AKA 브레드보드
빵판 AKA 브레드보드
반응형
빵판 AKA 브레드보드
BreadBoard's devlog
빵판 AKA 브레드보드
전체
오늘
어제
  • 분류 전체보기 (51)
    • iOS (8)
    • Swift (1)
    • RxSwift (2)
    • Algorithm (29)
      • Swift (7)
      • Python (9)
      • Java (12)
    • Error 정리 (3)
    • ETC (2)
    • CS (0)
    • Spring (1)
      • 일반 (0)
      • Spring Security (1)
    • Infra (0)
      • CI CD (0)
    • Project (4)
      • Vinyler (3)
      • BinBean (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • uicollectionview
  • github
  • Apple Enterprise Program
  • S3
  • CocoaPods
  • greedy알고리즘
  • 컴퓨터공학과
  • DFS
  • 다익스트라
  • Dijkstra
  • Apple Business Manager
  • xcode
  • SwiftPackageManager
  • TestFlight
  • 편입
  • IOS
  • 백준
  • RxSwift
  • AutoLayout
  • 최단경로
  • 알고리즘
  • BFS
  • framework
  • SPM
  • 코딩테스트
  • 개발자
  • AWS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
빵판 AKA 브레드보드
[BOJ] 2644. 촌수계산
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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