글 읽기 - 반례를 못찾겠습니다 고수님들 도와주세요

poppo99 5년 전 0

60% 쯤에 틀렸다고 나오는걸보니 반례가 있는 것 같습니다.

제가 놓친부분이 있을까요 ㅠㅠㅠ 아직 많이 부족한 것 같아 도움을 요청합니다 ㅠㅠ

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int StartingP,TargetP;//검색 시작위치 도착위치
    static int[][] result;
    static ArrayList<int []> Facelist;//인접행렬
    static boolean[] visited;//방문여부
    public static void main(String args[]){
        Scanner scanner=new Scanner(System.in);
        int Vertax=scanner.nextInt();
        Facelist=new ArrayList<>();
        result=new int[Vertax+1][Vertax+1];
        visited=new boolean[Vertax+1];
        for(int i=0;i<=Vertax;i++){
            int[] indexing=new int[Vertax+1];
            Facelist.add(indexing);
            visited[i]=false;
        }
        for(int i=1;i<=Vertax;i++){
            for(int j=1;j<=Vertax;j++){
                int tmp=scanner.nextInt();
                if (tmp==1){
                    Facelist.get(i)[j]=1;
                    result[i][j]=1;
                }

            }
        }

        for(int i=1;i<=Vertax;i++){
            for(int j=1;j<=Vertax;j++){
                StartingP=i;
                TargetP=j;
                if(result[StartingP][TargetP]==1){
                    continue;
                }
                else
                {
                    dfs(StartingP);
                    for(int tmp=0;tmp<visited.length;tmp++)
                        visited[tmp]=false;//다음검색을 위한 초기화
                }

            }
        }

        for(int i=1;i<result.length;i++){
            for(int j=1;j<result.length;j++){
                System.out.print(result[i][j]+" ");

            }
            System.out.println();
        }
    }

    public static void dfs(int startingP){
        visited[startingP]=true;

        for (int i=1;i<Facelist.get(0).length;i++){
            if(Facelist.get(startingP)[i]==1 && TargetP==i){
                result[StartingP][TargetP]=1;
                break;
            }
            else if(Facelist.get(startingP)[i]==1 && visited[i] ){
                result[StartingP][startingP]=1;
                for(int j=i+1;j<Facelist.get(0).length;j++){
                    if(Facelist.get(startingP)[j]==1 && !visited[j]){
                        result[StartingP][j]=1;
                        dfs(j);
                    }
                }
                break;
            }
            else{
                if(Facelist.get(startingP)[i]==1)
                {
                    result[StartingP][i]=1;
                    dfs(i);
                }

            }
        }
    }

}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다 고수님들 도와주세요

poppo99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말