[백준/java] 1260번 - DFS와 BFS

- 문제 : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

- 분류 : DFS, BFS

 

 

- 풀이

 

• BFS (너비우선탐색)
  • 가까운 정점을 먼저 방문하는 구조이기 때문에, 가까운 정점을 저장해두고 순서대로 방문할 수 있도록 선입선출 구조인 Queue를 사용한다.

• DFS (깊이우선탐색) 
  • 재귀 또는 스택을 사용해서 자기자신을 호출하는 순환 알고리즘 형태를 띈다.
  • 일단 한방향으로 갈 수 있는 데까지 깊이있게 파고든 다음에 다음으로 이동하는 방식.

 

 

import java.util.*;


class Node {
    int number; //정점 번호는 1번부터 N번까지
    LinkedList<Node> adjacent;
    boolean visited;
    
    public Node(int number) {
        this.number = number;
        this.visited = false;
        this.adjacent = new LinkedList<Node>();
    }
    
}

class Graph {
    Node[] nodes;
    
    public Graph(int nodeCount) {
        this.nodes = new Node[nodeCount];
        for(int i = 0; i<nodeCount; i++) {
            this.nodes[i] = new Node(i+1);
        }
    }
    
     public void addEdge(int a, int b) {
        Node aNode = this.nodes[a-1];
        Node bNode = this.nodes[b-1];
        
        if(!aNode.adjacent.contains(bNode)) {
            aNode.adjacent.add(bNode);
            // 여러개일 경우 작은 정점 먼저 방문하도록 정렬
            Collections.sort(aNode.adjacent, new Comparator<Node>() {
               @Override
               public int compare(Node a, Node b) {
                   return a.number > b.number ? 1: -1;
               }
            });
            
        }
        
        if(!bNode.adjacent.contains(aNode)) {
            bNode.adjacent.add(aNode);
            // 여러개일 경우 작은 정점 먼저 방문하도록 정렬
            Collections.sort(bNode.adjacent, new Comparator<Node>() {
               @Override
               public int compare(Node a, Node b) {
                   return a.number > b.number ? 1: -1;
               }
            });
        }
        
        
    }
    
    public void dfs(int v) {
        Node vNode = this.nodes[v-1];
        System.out.print(vNode.number + " ");
        vNode.visited = true;
        
        for(Node node: vNode.adjacent) {
            if(node.visited == false) {
                dfs(node.number);
            }
        }
    }

    public void bfs(int v) {
        Queue<Node> q = new LinkedList<Node>();
        Node vNode = this.nodes[v-1];
        q.add(vNode);
        vNode.visited = true;
      
        while(!q.isEmpty()){
            Node toVisit = q.peek();
            q.poll();
            System.out.print(toVisit.number + " ");
            
            if(!toVisit.adjacent.isEmpty()) {
                for(Node node : toVisit.adjacent) {
                    if(!node.visited) {
                        q.add(node);
                        node.visited = true;
                    }
                }
            } 
        }
    }
    
    //방문기록 초기화
    public void clearVisited() {
        for(Node node : this.nodes) {
            node.visited = false;
        }
    }

    
}



public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    
	    int nodeCount = sc.nextInt();
	    int edgeCount = sc.nextInt();
	    int v = sc.nextInt(); //startNode
	    
	    Graph g = new Graph(nodeCount);
	    
	    for(int i = 0; i<edgeCount; i++) {
	        int a = sc.nextInt();
	        int b = sc.nextInt();
	        
	        g.addEdge(a,b);
	    }
	    
	    g.dfs(v);
	   g.clearVisited();
	    System.out.println();
	    g.bfs(v);
	
	}
}