글 읽기 - 맞았는데 왜 맞았는지 모르겠어요.. (스포 주의)

coding11 3년 전 0

DFS로 풀었습니다.

제가 궁금한 점은

(4,5) - 3 - (1,2) 이런 식으로 그래프가 그려지면 될 것 같다고 생각하구요.

인접리스트로 구현해서

(4,3) (5,3) (3,1) (3,2)

ArrayList aa[앞의 숫자] = 뒤의 숫자 요렇게 했습니다.

제가 짠 코드에서 해당 숫자를 방문하게 되면 visit[숫자] = 1 을 넣어서 방문한 걸 표시해주고,

더이상 방문 안하게 설정해놨습니다.

결과적으로, 1과 2는 해당 메소드를 호출할 수 없고

3부터 호출할텐데 이때 visit[3] = 1을 해줘서 방문한 거를 표시해줍니다.

그런데, 제가 이 코드를 디버깅 하다보니까..

visit[3] =1이었었는데

-> aa[4]에서 3을 호출했더니

visit[3]이 0이어서 메소드를 재귀호출하더라구요.

아예 처음에 Main함수에서 for문이 돌때, i=3이면 3을 방문한걸로 쳤는데

갑자기 visit[3]이 왜 0이 되는지 아시는 분 계시면 답변부탁드립니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {	

	
	//static int arr[][] ; //10000 // 40000byte = 40KB =>1600KB => 1.6MB	
	//static int count;
	static int n,m;
	static int visit[];
	//static Queue qu ;
	static int an[];
	static ArrayList<Integer> aa[];
	
	public static void main(String[] args) throws IOException {
		
		//Scanner sc = new Scanner(System.in);
		// num = sc.nextInt(); // 총 케이스 수
		
		  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        StringTokenizer st = new StringTokenizer(br.readLine());
	         
	        n = Integer.parseInt(st.nextToken());
	        m = Integer.parseInt(st.nextToken());
		
			 aa = new ArrayList[n+1];
			 an = new int[n+1];
			 //초기화
			 for(int i=0; i<n+1; i++) {
				 aa[i]= new ArrayList<Integer>();
			 }
			
			 for(int i=0; i<m; i++) {
				 st = new StringTokenizer(br.readLine());
		            int a = Integer.parseInt(st.nextToken());
		            int b = Integer.parseInt(st.nextToken());
				 	 aa[a].add(b);
			 }
			 
			 for(int i=1; i<n+1; i++) {
				 visit = new int[n+1];
				 visit[i]=1;
				 method(i);

			 }
			 
			
			
			
		
			 int max = 0; 
			 for(int i=n; i>0; i--) {
				max = Math.max(max, an[i]);
			 }
			
			 StringBuilder sb = new StringBuilder();
			
			 for(int i=1; i<=n; i++) {
				 if(max==an[i]) {
					 sb.append(i+ " ");
				 }
			 }
			 
			 System.out.println(sb.toString());
		
		 }
		
		
		 
	
	
	
	public static void method(int b) {
		
	
		for(int xx : aa[b]) {
			if(visit[xx]==0) {
			
				an[xx]++;
				visit[xx]=1;
				method(xx);
		}	
			
			
		}
		
		
}
	
}

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

문제

문제

출처

ICPC

맞았는데 왜 맞았는지 모르겠어요.. (스포 주의)

coding11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말