[코딩테스트] 백준(BAEKJOON) - 촌수계산(Java, 2644번)

안녕하세요~

너무 오랜만에 다시 인사드리네요... 헤헤

 

사실은 코딩테스트 문제는 꾸준히 풀었으나 저의 게으름에 올리지 못했습니다. ㅠㅠ

 

하루에 한 문제 코딩테스트를 풀어보고자 하지만 쉽지 않네요~

 

문득 가만히 있다가 아 글다시 써야지! 라는 생각으로 이렇게 책상앞에 앉아 글을 남깁니다~

 

문제! 바로 만나보시죠~

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

2644번: 촌수계산

 

네 촌수계산입니다. DFS문제죠~

 

언제나 그렇듯 작성한 코드를 남기고나서 저만의 간단한 생각을 남겨보겠습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;



public class Main {

	static int n;
	static int t;
	static int[][] arr;
	static int start;
	static int end;
	static boolean[] visited;
	static boolean checker;
	static int count;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		String line="";
		int x=0;
		int y=0;
		checker=false;
		count=Integer.MAX_VALUE;
		
		n=Integer.parseInt(bf.readLine());
		
		arr=new int[n+1][n+1];
		visited=new boolean[n+1];
		
		line=bf.readLine();
		st=new StringTokenizer(line);
		
		start=Integer.parseInt(st.nextToken());
		end=Integer.parseInt(st.nextToken());
		
		t=Integer.parseInt(bf.readLine());
		
		for(int i=0;i<t;i++)
		{
			line=bf.readLine();
			st=new StringTokenizer(line);
			
			x=Integer.parseInt(st.nextToken());
			y=Integer.parseInt(st.nextToken());
			
			arr[x][y]=arr[y][x]=1;
		}
		
		visited[start]=true;
		
		for(int i=1;i<=n;i++)
		{
			
			if(arr[start][i]==1&&!visited[i])
			{
				visited[i]=true;
				dfs(i,1);
				visited[i]=false;
			}
		}
		
		if(checker)
			System.out.println(count);
		else
			System.out.println("-1");
			
		
	}
	
	static void dfs(int index, int len)
	{
		//count++;
		
		if(index==end)
		{
			count=Math.min(count, len);
			checker=true;
			return;
		}
			
		else
		{
			for(int i=1;i<=n;i++)
			{
				if(arr[index][i]==1&&!visited[i])
				{
					visited[i]=true;
					dfs(i,len+1);
					visited[i]=false;
				}
			}
				
		}
		
	}

}

어떤가요? 혹시 코드가 너무 길다고 생각되지는 않으실까요?

 

막상 제 생각을 들어보시면 오 뭐야 간단한데? 라고 생각이 드실수도 있습니다.

그럼 제 풀이 남겨보겠습니다.

 

① 문제에서 제공하는 정보를 입력받기

② 입력받은 n에서 +1 만큼 array 2중배열 만들기(저는 0부터 탐색보다 1부터 탐색이 편해 이렇게 합니다.)

③ 사람의 수n만큼 visited를 만들기(추후 visited는 촌수 계산에 제가 거쳐간 사람인지 체크합니다.)

④ 입력받은 t만큼 반복하면서 x,y 즉 관계를 설정하기 이때는 방향성이 없기에 [x][y], [y][x] 양방향으로 설정합니다.

⑤ 또한 여기서 찾아야될 관계는 시작점을 start, 도착점 end로 설정합니다.

⑥ 이제 촌수 탐색을 시작해보겠습니다.

⑦ 시작은 지정돼있습니다. 시작점인 start에 연결된 관계들을 하나씩 탐색합니다.

    - visited를 통해 해당 값과 촌수계산을 했는지 확인(!visited[index])하고 저와 관계가 맺어져 있는 사람인지(arr[x][y]==1) 확인합니다.

    - 연결돼 있는데 원하는 end의 값이 아니라면 dfs 함수를 통해 더 깊게 관계를 탐색합니다.

    - 탐색하면서도 역시 같은 조건을 탐색합니다. 만약 dfs의 index 값이 end, 즉 찾아야할 관계라면 종료합니다.

    - 다만 여기서 확인해야될 부분인 Math.min부분입니다.

    - dfs는 최소탐색의 수를 보장하지는 않습니다. 할아버지 아빠 나 이런방법이 있지만 dfs를 탐색하다보면 할아버지 큰아빠 아빠 나 이렇게 순서가 헛돌 수도 있다는거죠~

    - 그렇기에 최소값을 찾아줍시다. 또한 최소값을 찾기위해 한 번 탐색을 쫙돌았으면 visited를 초기화 해 다음 탐색에 문제가 없도록 해주시면 되겠습니다.

 

네~ 오늘은 이렇게 이번 코딩테스트 문제 풀어봤습니다.

 

비도 많이오고 날씨가 참 무덥네요.

식중독, 더위, 그리고 냉방병 조심하시길 바랍니다.

 

또 문제를 풀어서 돌아오겠습니다.

 

감사합니다😊