글 읽기 - 반례좀 찾아주세요...

kisay97 8년 전 0

원래 깊이우선탐색이나 넓이우선탐색으로 짜야 한다는건 아는데

인접행렬로 저 탐색들을 구현 할 줄 모르겠어서

인접행렬 만들고 그냥 인접행렬만큼 루프를 쫙 돌아서

if( 나랑 연결 되있고, 연결된 컴퓨터가 감염되 있다면){

나도 감염됨;

}

for( int i=1; i<컴퓨터갯수; i++){

if(감염확인배열[i]) count++;

}

이런식으로 짰습니다.

시간 초과가 나왔다면 이해를 하겠는데 그냥 틀렸다고 해서,

제가 아무렇게나 몇개 그림 그리고 그대로 입력해봤는데도 잘 나오더라고요;

반례좀 부탁드립니다!

import java.util.Scanner;

public class Problem2606 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int com = sc.nextInt();
		int link = sc.nextInt();
		
		int links[][] = new int[link][2];
		int matrix[][] = new int[com][com];
		
		int count = 0;
		int coms[] = new int[com];
		
		coms[0] = 1;
		
		//Make Adjacency matrix
		for(int i = 0; i < links.length; i++){
			for (int j = 0; j < links[i].length; j++) {
				links[i][j] = sc.nextInt();
			}
			
			matrix[ links[i][0] - 1 ][ links[i][1] - 1 ] = 1;
		}
		
		//Find Infected Computers
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				if(matrix[i][j] == 1 && coms[i] == 1){
					coms[j] = 1;
				}
			}
		}
		
		//count Infected Computers
		for (int i = 1; i < coms.length; i++) {
			if(coms[i] == 1) count++;
		}
		
		System.out.println(count);
	}
}

koosaga 8년 전 0

양방향으로 넣어주세요

matrix[ links[i][0] - 1 ][ links[i][1] - 1 ] = 1;

matrix[ links[i][1] - 1 ][ links[i][0] - 1 ] = 1;

kisay97 8년 전 0

양방향으로 넣어도 틀렸다고 나오네요 ㅠㅠ

import java.util.Scanner;

public class Problem2606 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int com = sc.nextInt();
		int link = sc.nextInt();
		
		int links[][] = new int[link][2];
		int matrix[][] = new int[com][com];
		
		int count = 0;
		int coms[] = new int[com];
		
		coms[0] = 1;
		
		//Make Adjacency matrix
		for(int i = 0; i < links.length; i++){
			for (int j = 0; j < links[i].length; j++) {
				links[i][j] = sc.nextInt();
			}
			
			matrix[ links[i][0] - 1 ][ links[i][1] - 1 ] = 1;
			matrix[ links[i][1] - 1 ][ links[i][0] - 1 ] = 1;
		}
		
		//Find Infected Computers
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				if(matrix[i][j] == 1 && coms[i] == 1){
					coms[j] = 1;
				}
			}
		}
		
		//count Infected Computers
		for (int i = 1; i < coms.length; i++) {
			if(coms[i] == 1) count++;
		}
		
		System.out.println(count);
	}
}

koosaga 8년 전 0

인접행렬을 루프를 돈다고 도달 가능성을 모두 파악할 수 있는 것이 아닙니다.

1 2 2 4 4 3 시도해보세요

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

문제

문제

출처

ICPC

반례좀 찾아주세요...

kisay97 8년 전 0

koosaga 8년 전 0

kisay97 8년 전 0

koosaga 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말