[SW Expert Academy]1949:등산로 조성

처음에 딱 봤을 때 [백준]말이되고 싶은 원숭이 문제가 떠올라서 BFS로 풀어야지 싶었다.

왜냐면 저번에 풀었던 기억(앗 파이썬으로 풀었었군)이 어렴풋이 있었기 때문!

그런데 생각보다 복잡한 문제였다..

1. 깎을때마다 달라지는 높이

2. DFS처럼 한 경로에 대한 최대 길이를 구해야함. (일반적으로 bfs의 visited배열에서는 방문했던 곳을 다시 큐에 넣지 않으므로)

3. 깎음 여부(이 부분만 원숭이랑 비슷했다...)

이 세가지 때문에 bfs의 늪에서 헤매다가 적절한 Node 클래스를 구성해서 풀었다.

class Node {
    int x, y, height;
    boolean isCut;
    int[][] vis;

    public Node(int x, int y, int height, boolean isCut, int[][] vis) {
        this.x = x;
        this.y = y;
        this.height = height;
        this.isCut = isCut; //깎음 여부
        this.vis = vis;
    }
}

 

 

Node 클래스 생성자에 visited 배열 선언할때 자괴감이...

그 배열을 또 큐에서 복사할때마다 또 자괴감이...

 

 

다들 DFS로 풀때 혼자 BFS로 풀고 힘들어하는 사람...이었지만 재미있었다^^!

 

결론: (풀고나니 dfs처럼 작동하는 bfs라서) DFS로 푸는게 나은듯. 

github.com/SuyeonChoi/Algorithms/blob/master/SW%20Expert%20Academy/Java/BFS.DFS/p1949.java

SuyeonChoi/Algorithms