글 읽기 - 도와주세요!!!

daye19415 7년 전 0

예제는 맞게 나오는데 자꾸 틀렸다고 결과나오네요.

다른 예제로도 풀어봤는데 맞는거 같은데 어디서 틀린건지 잘모르겠어요

알려주시면 감사하겠습니다!

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();//유저의 수 n
		int m=sc.nextInt();//관계의 수 m
		int[][] friend=new int[n][n];
		int a=0;
		int b=0;
		for(int i=0; i<m; i++){//친구관계 입력받기
			a=sc.nextInt();
			b=sc.nextInt();
			friend[a-1][b-1]=1;
			friend[b-1][a-1]=1;
		}
		int index=0;
		int[][] visited=new int[n][n];
		//단계의 합 구하기
		for(int i=0; i<n; i++){//유저 n명의 친구관계 구하기
			//dfs이용하여 구하기
			Stack myStack=new Stack();
			myStack.push(i);
			while(!myStack.isEmpty()){
				index=(int)myStack.pop();
				for(int j=0; j<n; j++){
					if(friend[index][j]==1&&visited[i][j]==0&&j!=i){//친구이면 stack에 저장(단, 방문한적 없어야 함&&자기자신은 안됨)
						myStack.push(j);
						visited[i][j]=visited[i][index]+1;
					}
				}			
			}
		}
		//가장 작은 사람 출력
		int min=(n-1)*(n-1);
		int sum=0;
		for(int i=0; i<n; i++){
			sum=0;
			for(int j=0; j<n; j++){
				sum+=visited[i][j];
			}
			System.out.println(i+": "+sum);
			if(min>sum){
				min=sum;
				index=i;
			}
		}
			System.out.println(index+1);		
	}
}

ljh6274 7년 전 0

bfs가 아닌 dfs로 탐색을 하셨네요

bfs였다면 위와같은식으로 하시면 아마 맞는 풀이법이 되었을텐데요, 스택을 사용한 dfs의 경우 먼저 방문을 한 정점이 나중에 방문할때보다 더 비용이 클 수 있습니다. 무슨 얘기냐면

만약 1 2, 1 3, 2 3, 3 4, 2 4, 2 5, 4 5 이런 경우를 생각해 보죠

그러면 정점 1에서 dfs를 통해 탐색을 하면 처음

pop 1 / 스택 - 2(1), 3(1) / top(3)

pop 3 / 스택 - 2(1), 4(2) / top(4)

pop 4/ 스택 - 2(1), 5(3) / top(5)

이러한 순서로 돌게 됩니다. 정점 옆의 괄호는 visited변수에 저장될 값입니다.

이로 인해 1->5는 3이라는 값이 저장되어 더 이상 변하지 않을것 입니다.

하지만 실제로는 1->(2, 3)->(4, 5)로 2라는 값이 저장되어야 하는거죠

그래서 스택을 돌면서 처음 도착한 정점이거나 아니면 이전에 저장된 값 보다 빠른 이동으로 왔을 경우 값을 갱신하여 주어야 합니다.

질문자님께서 작성하진 코드에서 if문을 약간 수정하면 되는데요, 스택에 도는 while문 내의 조건문을 아래와 같이 수정하시면 될것 같습니다.

if(friend[index][j]==1 && (visited[i][j]==0 || visited[i][j]>visited[i][index]+1)&& j!=i)

daye19415 7년 전 1

아 감사합니다 그 경우를 생각하지 못했네요

설명 너무 잘해주셔서 바로 이해가 되었네요 !! ㅎㅎ

돌려보니까 잘 돌아가네요

감사합니다!!!

댓글을 작성하려면 로그인해야 합니다.