글 읽기 - 1260 자바 질문 DFS, BFS..

park345601 5년 전 0

코드를 짜고 올라온 반례들을 질문게시판을 뒤져가며 어느정도 다 고친것 같은데

ArrayList[] a = (ArrayList[]) new ArrayList[n];

코드 중에 이부분에서

type safety :unchecked cast from ArrayList[] to ArrayList<Integer>[]

라고 뜨면서 SuppressWarnings 어노테이션을 붙이라고 뜨는데

이것때문에 코드가 틀렸다고 나올수도 있는건가요?

그리고 형식에 맞는게 아니면 어떻게 써야될까요..?

arraylist를 element로 갖는 배열을 만들고 싶었는데 잘 모르겠어서 도움부탁드립니다!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

// DFS (Depth First Search) -형제보다 자식버텍스를 우선 -스택사용
// BFS (Breadth First Search) -자식보다 형제버텍스를 우선 -큐사용
public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		String[] set = br.readLine().trim().split(" ");
		int n = Integer.parseInt(set[0]);
		int m = Integer.parseInt(set[1]); 
		int v = Integer.parseInt(set[2]);
		
		// [참고] https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/1260_AdjacencyList.java
		ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n];
		for (int i = 0; i < n; i++) a[i] = new ArrayList<>();
		ArrayList<Integer>[] _a = (ArrayList<Integer>[]) new ArrayList[n];
		for (int i = 0; i < n; i++) _a[i] = new ArrayList<>();
		
		// 각각의 vertex가 연결된 node들을 vertex-1번째 arraylist에 추가함
		for(int i = 0; i < m; i++) {
			String[] con = br.readLine().trim().split(" ");
			int num1 = Integer.parseInt(con[0]);
			int num2 = Integer.parseInt(con[1]);
			
			if(! a[num1 - 1].contains(num2 - 1)) {
				a[num1 - 1].add(num2 - 1);
				a[num2 - 1].add(num1 - 1);
				_a[num1 - 1].add(num2 - 1);
				_a[num2 - 1].add(num1 - 1);
			}
		}
		
		for(int i = 0; i < n; i++) Collections.sort(a[i]);
		for(int i = 0; i < n; i++) Collections.sort(_a[i]);
		
		dfs(n, m, v, a);
		bfs(n, m, v, _a);
		
		bw.close();
		br.close();
	}
	
	public static void dfs(int n, int m, int v, ArrayList<Integer>[] a) throws IOException {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(v - 1);
		for(int i = 0; i < n; i++)
			if(a[i].contains(v - 1)) 
				a[i].remove(a[i].indexOf(v - 1));
		ArrayList<Integer> outBuffer = new ArrayList<Integer>();
		outBuffer.add(v);
		int index = 1;
		
		while(index != n && !stack.isEmpty()) {
			if(! a[stack.peek()].isEmpty()) {
				int nv = a[stack.peek()].remove(0);
				if(a[nv].contains(stack.peek()))
					a[nv].remove(a[nv].indexOf(stack.peek()));
				stack.push(nv);
				if(!outBuffer.contains(nv + 1)) {
					outBuffer.add(nv + 1);
					index++;
				}
			}else stack.pop();
		}
		
		for(int i : outBuffer) bw.write(i + " ");
		bw.write("\n");
	}
	
	public static void bfs(int n, int m, int v, ArrayList<Integer>[] a) throws IOException {
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(v - 1);
		for(int i = 0; i < n; i++)
			if(a[i].contains(v - 1)) 
				a[i].remove(a[i].indexOf(v - 1));
		ArrayList<Integer> outBuffer = new ArrayList<Integer>();
		int index = 0;

		while(index != n && !que.isEmpty()) {
			if(!a[que.peek()].isEmpty()) {
				int p = que.peek();
				
				while(!a[p].isEmpty()) {
					int t = a[p].remove(0);
					que.offer(t);
					for(int j = 0; j < n; j++) 
						if(a[j].contains(t)) 
							a[j].remove(a[j].indexOf(t));
				}
			} else outBuffer.add(que.poll() + 1);
		}
		
		for(int i : outBuffer) bw.write(i + " ");
		bw.write("\n");
	}

}

djm03178 5년 전 1

그 부분은 관계 없다고 보입니다.

문제는 dfs를 하는 부분에 있는데, 중복 방문을 제거하기 위해 많은 노력을 하신 것 같지만 사실은 여전히 중복 방문이 일어날 수 있습니다.

아래와 같은 케이스에서 dfs는 1 2 3 4 5 6 을 출력해야 합니다.

dfs 문제에서 일반적으로는 간선을 제거하려고 할 필요가 없습니다. 정점에 방문 체크를 해주고, 이미 방문한 정점이면 단순히 스택이 넣지 않으면 되기 때문입니다. 지금처럼 일반적인 리스트에서 간선을 하나씩 지워내는 것은 시간복잡도상으로도 좋지 못합니다.

팁으로, dfs는 직접 스택을 이용하는 것보다 재귀 함수로 구현하는 것이 편합니다.

사실 지금의 dfs 코드를 보면, 어떤 정점을 방문한 뒤에 오직 하나의 인접한 정점만을 스택에 삽입하고 그 간선을 제거해버리고 있는데, 재귀를 이용하면 그 과정을 매우 편하게 할 수 있지만 지금처럼 반복문으로 해결하려고 할 때는 그보다는 먼저 현재 정점을 pop 해버린 다음, 이미 현재 정점을 방문한 적이 있다면 스킵하고, 아니라면 방문 여부를 표시하고 현재 정점에 연결된 간선을 역순으로 스택에 모두 한 번에 삽입해버리는 것이 낫습니다.

park345601 5년 전 0

감사합니다 덕분에 dfs코드를 방문여부체크를 통해서 해결하도록 바꿔서 문제는 맞췄습니다!

재귀함수로도 짜봐야겠네요!!

그리고 bfs도 방문여부로 체크하는게 시간복잡도를 줄일수있나요?

djm03178 5년 전 1

기본적으로 배열에서 원소 하나를 제거하는 건 O(배열에 들어있는 원소 수)만큼의 시간이 걸립니다. 해당 원소가 있는지 순회해서 찾아야 할 뿐만 아니라, 그 뒤에 있는 원소들을 전부 한 칸씩 앞으로 당겨와야 하기 때문입니다. 그래서 E개의 간선 모두를 제거하는 데에 최악의 경우 O(E^2)의 시간이 소요될 수 있습니다.

하지만 단순히 정점에 방문 체크를 해준다면 이러한 과정이 없이 E개의 간선을 도는 동안 V개의 정점에 체크만 해주면 되므로 O(E+V)로 시간복잡도를 크게 개선할 수 있습니다.

park345601 5년 전 0

재귀를 안썼는데도

dfs bfs 둘다 방문여부 확인으로 해줬더니 시간이 많이 줄어드네요

도움주셔서 감사합니다!!

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

문제

문제

출처

ICPC

1260 자바 질문 DFS, BFS..

park345601 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 1

park345601 5년 전 0

djm03178 5년 전 1

park345601 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말