BAEKJOON 1260번: DFS와 BFS

[2017-04-15 토요일]

* 내용: DFS와 BFS

1. 문제

2. 해결 방법

 

 

1. 문제

---

* 내용

- URL: https://www.acmicpc.net/problem/1260

* 예제 입출력: 문제의 테스트 케이스기 너무 적어서 직접 그리며 생성하였다.

번호	입력	출력
1	5 8 1 1 2 1 4 1 3 3 4 3 5 2 5 2 4 5 4	1 2 4 3 5 1 2 3 4 5
2	9 12 7 1 2 1 5 2 3 2 4 2 5 4 5 6 5 8 5 5 3 3 7 7 9 3 9	7 3 2 1 5 4 6 8 9 7 3 9 2 5 1 4 6 8
3	6 9 1 1 2 1 3 2 4 2 5 4 5 4 6 4 3 5 6 6 3	1 2 4 3 6 5 1 2 3 4 5 6
4	6 10 30000 30000 37 30000 40 30000 26 37 7 37 40 40 7 40 26 40 99 99 26 99 7	30000 26 40 7 37 99 30000 26 37 40 99 7

2. 해결 방법

---

* 이슈

A. break문의 올바르지 않은 사용 → break문 삭제 처리

B. 정렬 시킨 값을 세팅해주지 않아 제대로 정렬이 되지 않음

 

C. package 포함 시 계속해서 실패나는 현상

→ BAEKJOON 사이트에서 package 코드를 같이 넣으면 실패로 떨어진다.

이것 때문에 새벽까지 계속 매달렸다ㅠㅠ 그래도 덕분에 많은 도움이 되었다.

소스코드를 꼼곰하게 보고 무슨 에러가 있을지 다시 한 번 생각하는 습관을 기르는데 도움이 되었다...고 믿는다ㅠㅠ

 

* 소스코드

※ DFS와 BFS에 대해 이해하기 위해 따로 따로 작성 후 제출하여 중복된 소스코드가 많다.

package BAEKJOON; //제출 시에는 반드시 삭제
 
import java.util.*;
 
/**
 * Created by WindingRoad on 2017-04-15.
 */
 
@SuppressWarnings("Duplicates") // 중복 코드 표시 중지
public class BAEKJOON_1260 {
 
    private static int n;
    private static int m;
    private static int v;
    private static int[] edgeArr;
    private static Scanner scanner;
 
    // 테스트용
    public static void main(String args[]) throws Exception {
        int temp = 0;
 
        scanner = new Scanner(System.in);
 
        if (scanner.hasNextInt()) {
            temp = scanner.nextInt();
            if (temp >= 1 && temp <= 1000)
                n = temp;
            else
                return;
        }
        else {
            return;
        }
 
        if (scanner.hasNextInt()) {
            temp = scanner.nextInt();
            if (temp >= 1 && temp <= 10000)
                m = temp;
            else
                return;
        }
        else {
            return;
        }
 
        if (scanner.hasNextInt()) {
            temp = scanner.nextInt();
            v = temp;
        }
        else {
            return;
        }
 
        edgeArr = new int[m * 2];
 
        for (int i = 1; i <= m * 2; i++) {
            if (scanner.hasNextInt()) {
                temp = scanner.nextInt();
                edgeArr[i - 1] = temp;
            }
            else
                return;
        }
 
        // N(1≤N≤1,000), M(1≤M≤10,000)
        DepthFirstSearch depthFirstSearch = new DepthFirstSearch(n, m, v, edgeArr);
        depthFirstSearch.setListMap();
        depthFirstSearch.searchPath(v); // v: 시작 vertex
        depthFirstSearch.printResultPath();
 
        System.out.println();
 
        BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch(n, m, v, edgeArr);
        breadthFirstSearch.setListMap();
        breadthFirstSearch.searchPath(v); // v: 시작 vertex
        breadthFirstSearch.printResultPath();
    }
}
 
@SuppressWarnings("Duplicates") // 중복 코드 표시 중지
class DepthFirstSearch {
 
    private HashMap<Integer, Node> adjMap;
    private ArrayList<Integer> resultList;
    private ArrayList<Integer> nodeNumList;
 
    private int n;
    private int m;
    private int v;
    private int[] edgeArr;
 
    public DepthFirstSearch(int n, int m, int v, int[] edgeArr) {
        this.n = n;
        this.m = m;
        this.v = v;
        this.edgeArr = edgeArr;
    }
 
    public void setListMap() {
        adjMap = new HashMap<Integer, Node>();
        resultList = new ArrayList<>();
        nodeNumList = new ArrayList<>();
 
        for(int i = 1; i <= m * 2; i+= 2) {
            int v1 = edgeArr[i-1];
            int v2 = edgeArr[i];
 
            setNodeLink(adjMap, v1, v2);
        }
 
        for(Integer key : nodeNumList) {
            LinkedList<Integer> tempList = adjMap.get(key).getLinkedList();
            Collections.sort(tempList);
            adjMap.get(key).setLinkedList(tempList);
        }
 
        /*
        for(Integer key : nodeNumList) {
            System.out.println("key: " + key);
            for(Integer temp : adjMap.get(key).getLinkedList()) {
                System.out.print(temp + " ");
            }
            System.out.println("\n");
        }
        */
 
 
        // System.out.println(String.valueOf(v)); // 시작점
    }
 
    public void searchPath(int v) {
        if(adjMap.get(v).isVisited() == false) {
            adjMap.get(v).setVisited(true);
 
            // System.out.print(String.valueOf(v) + " "); // 출력
            resultList.add(v);
 
            for(Integer vertex : adjMap.get(v).getLinkedList()) {
                if(adjMap.get(vertex).isVisited() == false) {
                    searchPath(vertex);
                }
            }
        }
    }
 
    private void setNodeLink(HashMap<Integer, Node> adjMap, int v1, int v2) {
        if(adjMap.get(v1) != null) {
            if(!adjMap.get(v1).getLinkedList().contains(v2))
                adjMap.get(v1).getLinkedList().add(v2);
        }
        else {
            adjMap.put(v1, new Node(false, v2));
            adjMap.get(v1).getLinkedList().add(v2);
            nodeNumList.add(v1);
        }
 
        if(adjMap.get(v2) != null) {
            if(!adjMap.get(v2).getLinkedList().contains(v1))
                adjMap.get(v2).getLinkedList().add(v1);
        }
        else {
            adjMap.put(v2, new Node(false, v1));
            adjMap.get(v2).getLinkedList().add(v1);
            nodeNumList.add(v2);
        }
    }
 
    public void printResultPath() {
        int count = 0;
        int size = resultList.size();
        for(Integer temp : resultList) {
            if( (count + 1) == size ) {
                System.out.print( String.valueOf(temp) );
                count++;
            }
            else {
                System.out.print( String.valueOf(temp) + " " );
                count++;
            }
        }
    }
 
}
 
@SuppressWarnings("Duplicates") // 중복 코드 표시 중지
class BreadthFirstSearch {
 
    private HashMap<Integer, Node> adjMap;
    private Queue<Integer> pathQueue;
    private ArrayList<Integer> resultList;
    private ArrayList<Integer> nodeNumList;
 
    private int n;
    private int m;
    private int v;
    private int[] edgeArr;
 
    public BreadthFirstSearch(int n, int m, int v, int[] edgeArr) {
        this.n = n;
        this.m = m;
        this.v = v;
        this.edgeArr = edgeArr;
    }
 
    public void setListMap() {
        adjMap = new HashMap<Integer, Node>();
        resultList = new ArrayList<>();
        pathQueue = new LinkedList<>();
        nodeNumList = new ArrayList<>();
 
        for (int i = 1; i <= m * 2; i += 2) {
            int v1 = edgeArr[i-1];
            int v2 = edgeArr[i];
 
            setNodeLink(v1, v2);
        }
 
        for(Integer key : nodeNumList) {
            LinkedList<Integer> tempList = adjMap.get(key).getLinkedList();
            Collections.sort(tempList);
            adjMap.get(key).setLinkedList(tempList);
        }
 
        /*
        for(Integer key : nodeNumList) {
            System.out.println("key: " + key);
            for(Integer temp : adjMap.get(key).getLinkedList()) {
                System.out.print(temp + " ");
            }
            System.out.println("\n");
        }
        */
 
        // System.out.println(String.valueOf(v)); // 시작점
    }
 
    public void searchPath(int v) {
        if (adjMap.get(v).isVisited() == false) {
            adjMap.get(v).setVisited(true);
 
            // System.out.print(String.valueOf(v) + " "); // 출력
            resultList.add(v);
 
            for (Integer vertex : adjMap.get(v).getLinkedList()) {
                if (adjMap.get(vertex).isVisited() == false && !pathQueue.contains(vertex)) {
                    pathQueue.add(vertex); // Enqueue
                }
            }
 
            if(!pathQueue.isEmpty())
                searchPath(pathQueue.poll()); // Dequeue
        }
    }
 
    public void setNodeLink(int v1, int v2) {
        if(adjMap.get(v1) != null) {
            if(!adjMap.get(v1).getLinkedList().contains(v2))
                adjMap.get(v1).getLinkedList().add(v2);
        }
        else {
            adjMap.put(v1, new Node(false, v2));
            adjMap.get(v1).getLinkedList().add(v2);
            nodeNumList.add(v1);
        }
 
        if(adjMap.get(v2) != null) {
            if(!adjMap.get(v2).getLinkedList().contains(v1))
                adjMap.get(v2).getLinkedList().add(v1);
        }
        else {
            adjMap.put(v2, new Node(false, v1));
            adjMap.get(v2).getLinkedList().add(v1);
            nodeNumList.add(v2);
        }
    }
 
    public void printResultPath() {
        int count = 0;
        int size = resultList.size();
        for (Integer temp : resultList) {
            if ((count + 1) == size) {
                System.out.print(String.valueOf(temp));
                count++;
            } else {
                System.out.print(String.valueOf(temp) + " ");
                count++;
            }
        }
    }
 
}
 
class Node {
    private boolean visited;
    private int v;
    private LinkedList<Integer> linkedList;
 
    Node(boolean visited, int v) {
        this.visited = visited;
        this.v = v;
        linkedList = new LinkedList<>();
    }
 
    public boolean isVisited() {
        return visited;
    }
 
    public void setVisited(boolean visited) {
        this.visited = visited;
    }
 
    public LinkedList<Integer> getLinkedList() {
        return linkedList;
    }
 
    public void setLinkedList(LinkedList<Integer> linkedList) {
        this.linkedList = linkedList;
    }
}