글 읽기 - 다른 방식으로 맞긴했는데 이건 왜 안되는지 궁금합니다.

jeon9825 3년 전 0

어느 부분이 오류인지 궁금합니다.

모든 사람들이 연결되어있다고 해서 (무한대는 없다고 가정) 맨 처음에 n+1로 초기화를 시켜주었고요.

Queue로 BFS를 구현했습니다.

arr[i][j]가 1일때 queue에 값을 넣어서

solve() 함수에서 본인번호와 관계수를 가져와서

관계수를 비교해서 더 작은 값을 arr배열에 넣어준 건데 왜 안될까요....

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

public class Main {
	static int n;
	static int[][] arr;
	static boolean[][] visited;
	static Queue<Friend> q;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

		n = Integer.parseInt(tokenizer.nextToken()); // 유저 수

		arr = new int[n][n];
		visited = new boolean[n][n];
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = n + 1;
			}
		}

		int m = Integer.parseInt(tokenizer.nextToken()); // 관계 수
		for (int i = 0; i < m; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			int a = Integer.parseInt(tokenizer.nextToken()) - 1;
			int b = Integer.parseInt(tokenizer.nextToken()) - 1;

			arr[a][b] = 1;
			arr[b][a] = 1;
			visited[a][b] = true;
			visited[b][a] = true;
		}

		for (int i = 0; i < arr.length; i++) {
			q = new LinkedList<Friend>();
			for (int j = i + 1; j < arr[i].length; j++) {
				if (arr[i][j] == 1) {
					q.add(new Friend(j, arr[i][j]));
				}
			}
			solve(i);
		}

		int min = Integer.MAX_VALUE;
		int index = -1;
		for (int i = 0; i < arr.length; i++) {
			int sum = 0;
			for (int j = 0; j < arr[i].length; j++) {
				if (i == j)
					continue;
				sum += arr[i][j];
			}
			if (sum < min) {
				min = sum;
				index = i;
			}
		}
		System.out.println(index + 1);
	}

	static void solve(int index) {
		while (!q.isEmpty()) {
			Friend f = q.poll();
			int num = f.num;
			int dis = f.dis;
			for (int i = 0; i < n; i++) {
				if (i == index)
					continue;
				int pre = arr[index][i];
				if (!visited[index][i] && dis + arr[num][i] < pre) {
					arr[index][i] = dis + arr[num][i];
					arr[i][index] = dis + arr[num][i];
					visited[index][i] = true;
					visited[i][index] = true;
					q.add(new Friend(i, pre));
				}
			}
		}
	}
}

class Friend {
	int num;
	int dis;

	public Friend(int num, int dis) {
		this.num = num;
		this.dis = dis;
	}
}

shg9411 3년 전 1

1 - 7

2 - 7

3 - 6

4 - 10

5 - 10

반례입니다ㅏ

input
5 4
3 1
2 3
1 4
5 2

output
1

answer
3

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

문제

문제

출처

ICPC

다른 방식으로 맞긴했는데 이건 왜 안되는지 궁금합니다.

jeon9825 3년 전 0

shg9411 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말