백준 2644 촌수계산 Java

2023. 1. 12. 22:38· 알고리즘/BeakJoon

촌수 카운트를 어떻게 증가 시켜줘야 하는지 감을 못 잡아서 꽤 오래 걸린 문제다.

distance 정보를 담고 있는 배열을 추가시켜서 해당 원소 인덱스에 +1 씩 증가 시켜주는 식으로 해결했다.

package sliver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_2644 {
	
	/*
	 * 촌수를 계산해야 하는 두 사람의 번호를 기준으로
	 * list를 bfs를 돌아보고
	 * 안 나오면 -1 출력하고
	 * 아니라면 cnt++ 하다가 결과값 출력해보자
	 */
	
	static int N, M; //전체 사람 수
	static int [] arr; //찾아야 하는 원소들 넣어줄 배열
	static List<Integer>[] list; //그래프 만들어 줄 list
	static boolean [] visited; //방문 처리 배열
	static int [] dis; //각각의 거리를 넣어줄 배열

	//flag 변수
	static boolean flag;

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		arr = new int [2];
		
		//관계를 구해야 하는 두 원소를 배열에 채워주자
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<2; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		//인덱스와 원소 번호 맞춰주기
		list = new ArrayList[N+1];
		//안에 list 다시 넣어주기
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		M = Integer.parseInt(br.readLine());
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			list[from].add(to);
			list[to].add(from);
		}
		
		visited = new boolean [N+1];

		flag = false;
		dis = new int [N+1];
		
		bfs(arr[0], arr[1]);
		
		if(flag) {
			System.out.println(dis[arr[1]]);
		} else {
			System.out.println(-1);
		}
		

	}
	
	public static void bfs(int start, int end) {
		Queue<Integer> queue = new LinkedList<>();
		
		//일단 다 -1로 초기화
		for(int i=1; i<N+1; i++) {
			dis[i] = -1;
		}
		
		//큐에 시작점 집어넣고 방문처리
		queue.add(start);
		visited[start] = true;
		//시작점은 거리가 없으니까 0
		dis[start] = 0;
		
		while(!queue.isEmpty()) {
			int cur = queue.poll();

			
			//만약 종료지점에 도달했다면 그만!
			if(cur == end) {
				flag = true;
				break;
			} 
			
			for(int next : list[cur]) {
				if(!visited[next]) {
					visited[next] = true;
					queue.offer(next);
					//거리가 증가되는 것을 dis 배열에 표현해주자
					dis[next] = dis[cur] + 1;
				}
			}
			
		}
	}


}
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > BeakJoon' 카테고리의 다른 글

백준 1697 숨바꼭질 Java  (0) 2023.01.17
백준 7569 토마토 Java  (2) 2023.01.17
백준 1260 DFS와 BFS Java  (0) 2023.01.11
백준 17406 배열돌리기4 Java  (0) 2023.01.10
백준 2667 단지번호붙이기 Java  (0) 2023.01.05
'알고리즘/BeakJoon' 카테고리의 다른 글
  • 백준 1697 숨바꼭질 Java
  • 백준 7569 토마토 Java
  • 백준 1260 DFS와 BFS Java
  • 백준 17406 배열돌리기4 Java
개발자 정지은
개발자 정지은
프로그래밍 공부 기록
개발자 정지은
PROGRAMMING DIARY
개발자 정지은
전체
오늘
어제
  • 분류 전체보기 (107)
    • 알고리즘 (49)
      • BeakJoon (27)
      • SWEA (9)
      • Inflearn (2)
      • CodeSignal (1)
      • Programmers (10)
    • FE (0)
      • Javascript (0)
      • React (0)
    • BE (0)
    • CS공부 (13)
      • Database (7)
      • IT기본지식 (6)
    • TIL (45)
      • 프로그래머스 데브코스 (45)
    • Project (0)
      • DreamHi (0)
      • 인사관리시스템 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 코딩부트캠프
  • 알고리즘
  • ReactNative
  • javascript
  • 피그마
  • figma
  • 프론트엔드
  • React.JS
  • 국비지원교육
  • 자바스크립트
  • 프로그래머스 데브코스
  • 리액트

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
개발자 정지은
백준 2644 촌수계산 Java
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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