[java] 백준 2644 : 촌수계산

문제

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

2644번: 촌수계산

 

 

풀이

 

DFS

임의로 count를 만들어 dfs를 하기 전 count++를 계속했더니 틀린답이 나왔다 재귀함수 안에 count를 넣어줘야 맞게나옴

package main;
import java.util.*;


public class Main {
	static int N;
	static int M;
	static int C1;
	static int C2;
	static int count=0;
	static int answer=0;
	static ArrayList<Integer>[] arr;
	static boolean[] visited;
	
	public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);
	
	N = sc.nextInt(); //전체 사람의 수
	C1 = sc.nextInt(); //촌수 계산 1
	C2 = sc.nextInt(); //촌수 계산 2
	M = sc.nextInt(); //연결 수 
	
	visited = new boolean[N+1];
	arr = new ArrayList[N+1];
	
	for(int i=1; i<=N; i++) {
		arr[i] = new ArrayList<Integer>();
	}

	for(int i=1; i<=M; i++) {
		int x = sc.nextInt();
		int y = sc.nextInt();
		arr[x].add(y);
		arr[y].add(x);
		
	}
	
	//visited[C1]=true;
	DFS(C1,0);
	//BFS();
	if(visited[C2]==false) System.out.println(-1);
	else{System.out.println(answer);}
	}
	

	
	static void DFS(int v,int c) {
		visited[v]=true;
		if(v==C2) {answer=c; return;}
		for(int x:arr[v]) {
			if(visited[x]==false) {
				DFS(x,c+1);
					}
		}
		
		
		
	}
	
}

 

 

BFS

방문배열이랑 거리배열 둘 다 사용

package main;
import java.util.*;


public class Main {
	static int N;
	static int M;
	static int C1;
	static int C2;
	static int count=0;
	static int answer=0;
	static ArrayList<Integer>[] arr;
	static boolean[] visited;
	static 	int[] dis;
	public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);
	
	N = sc.nextInt(); //전체 사람의 수
	C1 = sc.nextInt(); //촌수 계산 1
	C2 = sc.nextInt(); //촌수 계산 2
	M = sc.nextInt(); //연결 수 
	dis = new int[N+1];
	visited = new boolean[N+1];
	arr = new ArrayList[N+1];
	
	for(int i=1; i<=N; i++) {
		arr[i] = new ArrayList<Integer>();
	}

	for(int i=1; i<=M; i++) {
		int x = sc.nextInt();
		int y = sc.nextInt();
		arr[x].add(y);
		arr[y].add(x);
		
	}
	
	//visited[C1]=true;
	//DFS(C1,0);
	BFS();
	if(visited[C2]==false) System.out.println(-1);
	else{System.out.println(dis[C2]);}
	}
	
		
		
		
	}
	static void BFS() {
		Queue<Integer> q = new LinkedList<>();
		q.add(C1);
		visited[C1]=true;
	
		while(!q.isEmpty()) {
			int now = q.poll();
			for(int x : arr[now]) {
				if(visited[x]!=true) {
					
					visited[x]=true;
					dis[x]=dis[now]+1;
					q.add(x);
					if(x==C2) {return;}
				}
			}
			
		}
		
	}
}

 

 

 

효율적이지 못한 것 같아 거리배열만 사용해도 방문했는지 알 수 있으니까 거리배열만 사용하기로 수정

거리값이 0이면 방문하지 않았으므로 -1출력

package main;
import java.util.*;


public class Main {
	static int N;
	static int M;
	static int C1;
	static int C2;
	static int count=0;
	static int answer=0;
	static ArrayList<Integer>[] arr;
	static boolean[] visited;
	static 	int[] dis;
	public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);
	
	N = sc.nextInt(); //전체 사람의 수
	C1 = sc.nextInt(); //촌수 계산 1
	C2 = sc.nextInt(); //촌수 계산 2
	M = sc.nextInt(); //연결 수 
	dis = new int[N+1];
	visited = new boolean[N+1];
	arr = new ArrayList[N+1];
	
	for(int i=1; i<=N; i++) {
		arr[i] = new ArrayList<Integer>();
	}

	for(int i=1; i<=M; i++) {
		int x = sc.nextInt();
		int y = sc.nextInt();
		arr[x].add(y);
		arr[y].add(x);
		
	}
	
	//visited[C1]=true;
	//DFS(C1,0);
	BFS();
	if(dis[C2]==0) System.out.println(-1);
	else{System.out.println(dis[C2]);}
	}
	

	static void BFS() {
		Queue<Integer> q = new LinkedList<>();
		q.add(C1);
		
		while(!q.isEmpty()) {
			int now = q.poll();
			for(int x : arr[now]) {
				if(dis[x]==0) {
                
					dis[x]=dis[now]+1;
					q.add(x);
					if(x==C2) {return;}
				}
			}
			
		}
		
	}
}