글 읽기 - 반례를 도저히 못찾겠어요

ghdtmdwo123 4년 전 0

어디가 틀렸는지 도저히 모르겠네요 ;;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class b1976 {

	static int n;
	static int m;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		n  = Integer.parseInt(str1);
		
		String str2 = br.readLine();
		m  = Integer.parseInt(str2);
		
		int map[] = new int[n+1];
		
		for(int i = 1 ; i <= n; i++) {
			map[i]= i;
		}
		
		for(int i = 1; i <= n; i++) {
			String str[] = br.readLine().split(" ");
			for(int j = 1;  j <= n; j++) {
				int a  = Integer.parseInt(str[j-1]);
		
				if(a==1) { // 집합
					union(i,j,map);
				}
				
			}
			
		} // 이중 포문
		
		String str[] = br.readLine().split(" ");
		
		int b = map[Integer.parseInt(str[0])]; 
		
		boolean check =false;
		
		for(int i = 0 ; i < m; i++) {
			
			int a  = map[Integer.parseInt(str[i])];
			if(a!=b) {
				check = true;
				break;
			}
			b = a;
		}
		
		if(!check)System.out.print("YES");
		else System.out.print("NO");
		
		
	
	} // main

	static void union(int x, int y, int map[]) {
		
		x = find(x,map);
		y = find(y,map);
		
		if(x != y) {
				
			map[y] = x;	
			
		}
		
		
	}
	
	static int find(int x, int map[]) {
		
		if(x == map[x]) {
			return x;
		}else {
			return map[x] = find(map[x],map);
		}
		
		
	}
	
	
} // class

wagurano 4년 전 0

그냥 map배열로 비교하니깐 틀립니다.

find(1) != find(i)로 비교해야하네요.

저도 왜그런지는 좀 알아보는중입니다.

skysign 3년 전 0

47번 라인의 코드에 문제가 있구요,

아래 영상의 마지막 부분에 관련된 내용이 설명되어 있습니다.

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

문제

문제

출처

ICPC

반례를 도저히 못찾겠어요

ghdtmdwo123 4년 전 0

wagurano 4년 전 0

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말