[백준/Java] 1260_BFS/DFS (1)

뒤에 1이 붙은 이유는 2~3일간 고심끝에 완성한 코드임에도 장엄한 틀렸습니다!가 떴기 때문이당 ㅎ

 

정말 슬프다. DFS/BFS를 큐와 스택으로 구현하지 않고 그냥 내가 생각했을때 맞는 방법으로 구현해 보았는데 .. 휴 역시 아닌가 ㅠㅠ 약간 속상쓰 ..

 

일단 지금까지 구현해놓은 내용을 정리해서 포스팅 하고 새로운 방법으로 구현해 보고 다시 포스팅할 예정이다. 후 정말 성공했음 좋겠다~

 

 

 

 

 

문제에서 input이 들어오는 방식을 첫 줄에 노드의 갯수, 라인 정보의 갯수, 시작 노드 인덱스가 차례로 들어오고 다음줄 부터 라인 정보가 들어온다.

5 4 4
1 5
2 3
2 4
3 5

이렇게 인풋이 들어오면 5개의 노드가 총 4개의 연결정보를 가지고 있고 4번 노드부터 탐색을 시작하라는 의미이다.

 

 

 

 

 

일단 지금 구현해 놓은 방법은 아래와 같다. 아래 코드들은 Input을 읽고 2d array를 사용해서 그래프를 표시하는 코드이다

public static void main(String[] args) throws IOException {
        //BufferedReader와 BufferedWriter를 사용해서 input을 가져옴
        StringTokenizer st = new StringTokenizer(br.readLine());

        int numberOfNode = Integer.parseInt(st.nextToken());
        int numberOfLine = Integer.parseInt(st.nextToken());
        int startNode = Integer.parseInt(st.nextToken());

        List<Integer> result = new ArrayList<>();

        //bfs검사용, dfs 검사용 노드를 따로 만듦. 여기도 개선의 여지가 보인다
        int[][] bfsNodes = new int[numberOfNode][numberOfNode];
        int[][] dfsNodes = new int[numberOfNode][numberOfNode];

        for(int i=0;i<numberOfLine;i++){
            st = new StringTokenizer(br.readLine());
            int leftNode = Integer.parseInt(st.nextToken()) - 1;
            int rightNode = Integer.parseInt(st.nextToken()) - 1;

            //visited된 노드를 1로 표시. 양방향 노드라고 간주했으므로 두 군데 모두 표시해 줘야한다
            bfsNodes[leftNode][rightNode] = 1;
            bfsNodes[rightNode][leftNode] = 1;

            dfsNodes[leftNode][rightNode] = 1;
            dfsNodes[rightNode][leftNode] = 1;
        }

        DFS(dfsNodes, startNode-1, numberOfNode, result); //Do DFS
        printResult(result);

        BFS(bfsNodes, startNode-1, numberOfNode, result); //Do BFS
        printResult(result);

        bw.flush();
        bw.close();
    }

 

 

 

 

 

DFS

DFS가 조금 더 만만하니 ㅎㅎ DFS를 먼저 소개해보겠다.

 

1. DFS는 깊게 깊게 들어가는 구조이다. 노드를 탐색하다 연결되어 있는 노드를 만나면 그 노드를 일단 결과에 넣는다.

2. 그리고 다시 그 노드에서 깊게 들어가서 연결된 노드를 찾는다.

3. 모든 노드를 한번씩 다 찾아봤다면 더이상 찾아볼 필요가 없다

 

위 순서로 생각했더니 재귀스럽게 풀어야 겠다는 결론이 나왔다.

private static void DFS(int[][] nodes, int tartgetNode, int numberOfNode, List<Integer> result) {

        if(result.size() == numberOfNode) return; //3
        result.add(tartgetNode);//1

        for (int j = 0; j < numberOfNode; j++) { //2
            if(nodes[tartgetNode][j] != 1) continue; //연결이 되어 있지 않으면 검사할 필요 없음

            //찾았다고 표시
            nodes[tartgetNode][j] = -1;
            nodes[j][tartgetNode] = -1;

            DFS(nodes, j, numberOfNode, result);
        }

    }

흠 잘 한것 같은데 틀렸다 ㅠㅠ 아마 저기 3번을 구현한 부분을 다시 생각해야 할 것 같다.

 

백준에서는 연결되지 않는 노드는 애초에 사용하지 않는것 같다. 그렇다면 queue나 stack처럼 리스트를 활용할 만한 방향을 찾아야 할 것 같기도 ...

 

 

 

 

 

BFS

1. BFS는 옆으로 길게길게 뻗는 구조이다. 

2. 시작 노드에서 연결된 모든 노드를 찾는다. 그러다가 연결된 노드가 나오면 그 노드를 다음 노드로 찜꽁한다.

3. 더이상 연결된 노드가 없을때까지 계속한다

private static void BFS(int[][] nodes, int tartgetNode, int numberOfNode, List<Integer> result) {

        int nextNode = tartgetNode;

        while(nextNode != -1) { //3

            System.out.println("[Result] => " + result);
            System.out.println("[tartgetNode] => " + tartgetNode);

            if(result.indexOf(tartgetNode) == -1) result.add(tartgetNode);

            for (int j = 0; j < numberOfNode; j++) {
                if(nodes[tartgetNode][j] != 1) continue; //연결이 되어 있지 않으면 검사할 필요 없음
                if(result.indexOf(j) == -1) result.add(j); //1

                //찾았다고 표시
                nodes[tartgetNode][j] = -1;
                nodes[j][tartgetNode] = -1;

                //next node 찾기
                for (int k = 0; k < numberOfNode; k++) {//2
                    if (nodes[j][k] == 1) {
                        nextNode = nodes[j][k];
                        break;
                    }
                }
            }

            if(nextNode != -1) tartgetNode = nextNode;
        }

    }

여기도 아마 다음 노드로 나아가는 방향이 잘못된것 같다.

 

 

 

 

 

 

이렇게 포스팅을 하다보니 next node를 선정하는 방법과 탐색을 종료하는 기준에서 뭔가 문제가 있어보인다. 요 부분을 보완하면 잘 될 것 같은 느낌 .. !! 느낌만 이런건지 모르겠으나 ㅋㅋㅋ

 

 

 

조속히 2탄으로 돌아와 이 여정의 끝을 알리고 싶다.