[Java/백준/DFS와 BFS] 1260 - DFS와 BFS

문제

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

틀린 코드

예제 2번

5 5 3

5 4

5 2

1 2

3 4

3 1

정답>>

3 1 2 5 4

3 1 4 2 5

이어야 하는데...

 

내 코드는

3 1 2 5 4
3 4 1 5 2

이렇게 나온다. 아마 addEdge할 때 순서대로 LinkedList 안에 넣기 때문에 그런거 같다..

addEdge를 하는 과정을 좀 더 생각해봐야겠다.

 

import java.util.LinkedList;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.Stack;
import java.util.NoSuchElementException;
import java.util.Scanner;

class Queue<T>{
	class Node<T>{
    	private T data;
        private Node<T> next;
        
        public Node(T data){
        	this.data = data;
        }
    }
    
    private Node<T> first;
    private Node<T> last;
    
    public void add(T item){
    	Node<T> t = new Node<T>(item);
        
        if(last != null){
        	last.next = t;
        }
        last = t;
        //큐가 비어있을 때
        if(first == null){
        	first = last;
        }
    }
    public T remove(){
    	if(first == null)
			throw new NoSuchElementException();
        
        T data = first.data;
        first = first.next;
        
        if(first == null)
        	last = null;
            
        return data;
    }
    
    public T peek(){
    	if(first == null)
        	throw new NoSuchElementException();
        return first.data;
    }
    
    public boolean isEmpty(){
    	return first == null;
    }	
}

class Graph{
	class Node{
		int data;
		LinkedList<Node> adjacent;
		boolean marked;
		
		Node(int data){
			this.data=data;
			this.marked=false;
			adjacent = new LinkedList<Node>();
		}
	}
	
	Node[] nodes;
	ArrayList<Integer> dfsAns;
	ArrayList<Integer> bfsAns;
	Graph(int size){
		nodes = new Node[size];
		for(int i=0; i<size; i++) {
			nodes[i] = new Node(i+1);
		}
	}
	
	void addEdge(int i1, int i2) {
		Node n1 = nodes[i1-1];
		Node n2 = nodes[i2-1];
		
		if(!n1.adjacent.contains(n2)) {
			n1.adjacent.add(n2);
		}
		if(!n2.adjacent.contains(n1)) {
			n2.adjacent.add(n1);
		}
	}
	
	ArrayList dfs(int index) {
		dfsAns = new ArrayList<>();
		Node root = nodes[index-1];
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		root.marked = true;
		
		while(!stack.isEmpty()) {
			Node r = stack.pop();
			for(Node n : r.adjacent) {
				if(n.marked==false) {
					n.marked=true;
					stack.push(n);
				}
			}
			dfsAns.add(r.data);
		}
		return dfsAns;
	}
	
	ArrayList bfs(int index) {
		bfsAns = new ArrayList<>();
		Node root = nodes[index-1];
		Queue<Node> queue = new Queue<Node>();
		queue.add(root);
		root.marked = true;
		while(!queue.isEmpty()){
			Node r = queue.remove();
			for(Node n : r.adjacent) {
				if(n.marked==false) {
					n.marked=true;
					queue.add(n);					
				}
			}
			bfsAns.add(r.data);		
		}
		return bfsAns;
	}
	
	void resetMark() {
		for(int i=0; i<nodes.length; i++) {
			nodes[i].marked = false;
		}
	}
}
class Main{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int M = in.nextInt();
		int V = in.nextInt();
		
		Graph g = new Graph(N);
		//addEdge
		for(int i=0; i<M; i++) {
			g.addEdge(in.nextInt(), in.nextInt());
		}
		
		ArrayList<Integer> ans1 = g.dfs(V);
		g.resetMark();
		ArrayList<Integer> ans2 = g.bfs(V);
		
		for(int i=0; i<ans1.size(); i++) {
			if(i==ans1.size()-1)
				System.out.println(ans1.get(i));
			else
				System.out.print(ans1.get(i)+" ");
		}
		for(int i=0; i<ans2.size(); i++) {
			if(i==ans2.size()-1)
				System.out.println(ans2.get(i));
			else
				System.out.print(ans2.get(i)+" ");
		}
		in.close();
	}
}

 

더 간결해진 코드

developer-mac.tistory.com/63

[Java]백준 1260번 :: DFS와 BFS

 

DFS는 확실히 재귀가 빠르다.

인접하는 노드를 저장하는 것은 Node 클래스를 이용하는 대신 ArrayList<Integer>의 배열을 사용했다.

덕분에 sort도 시킴 ㅎㅎ

 

import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.Scanner;
import java.util.Queue;

class Main{
	static ArrayList<Integer>[] adjacent;
	static int N;
	static boolean[] marked;
	
	private static void dfs(int pos){
		marked[pos] = true;
		System.out.print(pos+" ");
		for(int node : adjacent[pos]) {
			if(!marked[node])
				dfs(node);
		}
	}
	
	private static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(start);
		marked[start] = true;
		
		while(!queue.isEmpty()) {
			int first = queue.poll();
			System.out.print(first+" ");
			for(int node : adjacent[first]) {
				if(!marked[node]) {
					marked[node] = true;
					queue.add(node);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		int M = in.nextInt();
		int V = in.nextInt();
		
		//initialize list
		adjacent = new ArrayList[N+1];
		for(int i=1; i<=N; i++) {
			adjacent[i] = new ArrayList<Integer>();
		}
		
		//add Edge
		for(int i=0; i<M; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			
			adjacent[a].add(b);
			adjacent[b].add(a);
		}
        //sort edge
		for(int i=1; i<=N; i++) {
			Collections.sort(adjacent[i]);
		}
		
		marked = new boolean[N+1];
		dfs(V);
		System.out.println();
		
		marked = new boolean[N+1];
		bfs(V);
		System.out.println();
		
		in.close();
	}
}