글 읽기 - 무엇이 틀렸을까요? 도와주세요 ㅠㅠㅠㅠ

chsong91 4년 전 0

오랜만에 회귀해서 1번부터 푸는데

틀리네요 그것도 세번이나 ㅠㅠ

전혀 모르겠네요 반례도 찾아보고 예제도 다른거 여러번 넣어보는데...

지적은 달게 받겠습니다.. 부디 도와주세요 고수님들!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
	
	private static int n, m, s;
	private static boolean[][] line;
	private static boolean[] check;
	private static ArrayList<Integer> al = new ArrayList<Integer>();
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		line = new boolean[n+1][n+1];
		check = new boolean[n+1];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int l1 = Integer.parseInt(st.nextToken());
			int l2 = Integer.parseInt(st.nextToken());
			line[l1][l2] = true;
			line[l2][l1] = true;
		}
		
		for (int i = 0; i < 2; i++) {
			if(i == 0) dfs(s, check);
			if(i == 1) bfs(s, check);
			for (int j = 0; j < al.size(); j++) {
				System.out.print(al.get(j) + " ");
			}
			System.out.println();
			al.clear();
		}
		br.close();
		
	}
	public static void dfs(int start, boolean[] check) {
		boolean[] a = check.clone();
		al.add(start);
		a[start] = true;
		for (int i = 1; i <= n; i++) {
			if(i == start) continue;
			if(a[i] || !line[start][i]) continue;
			a[i] = true;
			dfs(i,a);
			break;
		}
	}
	public static void bfs(int start, boolean[] check) {
		Queue<Integer> qu = new LinkedList<Integer>();
		boolean[] a = check.clone();
		a[start] = true;
		qu.add(start);
		while(!qu.isEmpty()) {
			int now = qu.poll();
			al.add(now);
			for (int i = 1; i <= n; i++) {
				if(i == now) continue;
				if(a[i] || !line[now][i]) continue;
				a[i] = true;
				qu.add(i);
			}
		}
	}
	
	
}	

djm03178 4년 전 1

50번째 줄의 존재 이유를 모르겠습니다. 단 하나의 연결된 정점만 발견했다고 해서, 그 정점으로부터 탐색이 끝나면 다른 정점이 또 연결되어있는지는 확인하지 않겠다는 뜻인가요?
dfs 호출 시마다 check 배열을 clone을 하면 안 되고, 그 배열 그대로를 사용해야 합니다.

chsong91 4년 전 0

djm03178님 지적 정말 고맙습니다.

check배열은 false로 초기화해주는 메소드를 만들어서 전역변수로 사용하여 해결하였고 50번째 줄을 지우고 add를 진입할때 넣어주니 해결되었습니다.

정말 감사합니다. 아직도 많이 부족하네요 ㅠㅠ

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

문제

문제

출처

ICPC

무엇이 틀렸을까요? 도와주세요 ㅠㅠㅠㅠ

chsong91 4년 전 0

djm03178 4년 전 1

chsong91 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말