글 읽기 - 반례가 있는걸까요?

kde6260 6년 전 0

링크리스트로 구현했습니다. 작은번호부터 탐색하기 때문에 간선 입력받을 때마다 리스트 내에 있는 정점들과 비교해서 삽입합니다.

배열 초기화도 하고 V가 1에서 1000사이가 아닐 수도 있다고 해서 V가 hashMap의 키 집합에 존재하는지로 예외처리 했습니다.

BFS에서도 큐에 add하기 전에 if문으로 방문여부 거르는데 어디서 문제인지 모르겠네요ㅜㅜ

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;


public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		if(N>1000 || N<1) return;
		
		int M = sc.nextInt();
		if(M>10000 || M<1) return;
		
		int V = sc.nextInt();
		
		Map<Integer, LinkedList<Integer>> list = new HashMap<Integer, LinkedList<Integer>>();
		
		for(int i=1; i<=M; i++){
			int first = sc.nextInt();
			int sec = sc.nextInt();

			//처음 입력되는 정점이면
			if(list.get(first)==null){
				LinkedList<Integer> adj = new LinkedList<Integer>();
				adj.add(sec);
				list.put(first, adj);
			}
			else{ //중복되는 간선 체크
				for(int element: list.get(first)){
					if(element==sec) continue;
				}
				
				// 정점이 여러개 있을 때 번호가 작은 것 부터 방문하기 위해 오름차순으로 리스트에 삽입.
				LinkedList<Integer> sublist = list.get(first);
				int idx = sublist.size()-1;
				while(idx>=0){
					int num = sublist.get(idx);
					if(num<=sec) {
						sublist.add(idx+1, sec);
						break;
					}
							
					else idx--;
				}
				if(idx==-1) 
					sublist.addFirst(sec);	
					
			}
		}
		
		boolean exist = false;
		for(int key: list.keySet()){
			if(key==V) {
				exist = true;
				break;
			}
		}
		if(!exist) return;
		
		//큐는 int형		
		Queue<Integer> q = new LinkedList<Integer>();
		
		// 각 노드의 방문여부 저장
		boolean [] DFSvisited = new boolean[N+1];
		boolean [] BFSvisited = new boolean[N+1];
		Arrays.fill(DFSvisited, false);
		Arrays.fill(BFSvisited, false);
		q.add(V);
		DFS(DFSvisited, list, V);
		System.out.println();
		BFS(BFSvisited, q, list);

	}
	
	
	public static void DFS(final boolean[] visited, Map<Integer, LinkedList<Integer>> list, int v){
		// 재귀호출 시간복잡도 = O(n+m)
		visited[v] = true;
		System.out.print(v+" ");
		LinkedList<Integer> sublist = list.get(v);
		if(sublist!=null){
			for(int element: sublist){
				if(!visited[element]){
					DFS(visited, list, element);
				}
			}
		}
		
	}
	
	public static void BFS(boolean[] visited, Queue<Integer> q, Map<Integer, LinkedList<Integer>> list){
		
		// 순회할 때 시간복잡도 = O(n+m)
		while(!q.isEmpty()){
			int num = q.poll();
				System.out.print(num+" ");						
				visited[num] = true;
				if(list.get(num)!=null){
					for(int node: list.get(num)){
						if(!q.contains(node) && !visited[node])
							q.add(node);
					}
				}	
			}
	}
}

djm03178 6년 전 1

일단, 질문 게시판 공지사항 https://www.acmicpc.net/board/... 에 있는 "질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요." 를 앞으로는 숙지해주시기 바랍니다.

먼저 "입력으로 주어지는 간선은 양방향이다."를 놓치셨습니다. 이는 꼭 왼쪽의 정점에서 오른쪽 정점으로만 갈 수 있는 것이 아니라 그 반대 방향으로도 갈 수 있다는 뜻입니다. 다음과 같은 입력에서 모두 2 1이 나와야 합니다.

2 1 1

2 1

그리고 코드에 불필요한 부분들이 보이는데 먼저 "V가 1에서 1000사이가 아닐 수도 있다고 하는" 것은 문제 어디에도 써있지 않습니다. 정점 번호는 모두 1에서 1000 사이이고 간선들도 모두 이들 사이만 연결합니다. 그리고 입력 조건을 코드에 넣을 필요는 없습니다.13~16번째 줄은 불필요합니다.

또한 BFS의 시간복잡도는 본래 O(V+E)가 맞으나, 104번째 줄처럼 q.contains 같은 것이 들어가면 O(V(V+E))가 됩니다. q.contains는 큐에 들어간 모든 원소를 검사하기 때문에 최대 정점의 수만큼의 시간이 매번 필요합니다. 가장 기본적인 해결 방법은 큐에서 원소를 빼낸 후가 아닌, 큐에 원소를 넣을 때 바로 visit 체크를 해버리는 것입니다. 그러면 큐에 원소가 있는지를 판별할 필요가 없습니다.

사실 이 문제를 간편하게 푸는 방법은 원소를 링크드 리스트 대신에 인접 행렬 (2차원 배열)로 만들어서 간선을 연결하는 것인데, 그러면 간선을 오름차순으로 따로 정렬하거나 중복을 제거하는 과정이 불필요합니다.

kde6260 6년 전 0

답변 감사합니다ㅜㅜ

hdnua 6년 전 0

@djm03178

실례지만 입력 2 1 1 2 1 에서 출력이 2 1이 나오는 이유가 궁금합니다.

세 번째 인자는 방문을 시작한 정점이어서 가장 처음에 나와야 하므로 1 2가 옳은 순서가 아닌지요?

djm03178 6년 전 1

헉 제가 오타를 낸 것 같습니다. 입력의 세 번째 수는 2가 되어야 합니다. 제보 감사합니다.

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

문제

문제

출처

ICPC

반례가 있는걸까요?

kde6260 6년 전 0

djm03178 6년 전 1

kde6260 6년 전 0

hdnua 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말