Doby's Lab

이번 문제에서 크게 어려웠던 점은 없었으나 각 문제에 대한 포인트를 항상 블로그에 담아두려 하기 때문에 가져왔다. 문제에서 헷갈릴 수 있는 건 visited의 리셋이었다. 비의 높이에 따라 bfs를 해주며 건물의 개수를 cnt하며 배열에 따로 담았었다. 하지만, cnt를 담은 배열을 디버깅해보니 처음을 제외하고는 전부 0이었다. 이 부분에서 visited를 초기화시키지 않았구나라는 것을 알고 reset 함수를 작성하고, 비에 높이에 따라 건물 cnt가 끝날 때마다 reset 함수를 콜 해주었다. [코드] #include #include #include #include using namespace std; int map[101][101] = { 0, }; bool visited[101][101] = { 0..

이번 문제 풀이는 못 풀어서 다른 사람의 답을 참고했음에도 성취감을 느낄 수 있었다. 주석처리가 이번 문제의 성취감 포인트였던 거 같다. 기존의 문제 풀이 방식 for문을 사용하여 1일 때, BFS를 사용하면 한 번에 모든 0인 노드를 다 순회하기 때문에 다른 접근법이 필요했다. 떠올랐던 방법이 for문을 사용하여 1일 때, BFS를 사용하지 않고, 큐에다가 그 노드를 push 한다. 그리고 난 뒤에 BFS를 실행시키면 답에 접근할 수 있었다. 하지만, 또 다른 문제가 발생한다. 현재까지의 접근법으로 작성한 코드는 이렇다. // 궁금증 1: 굳이 이번 문제에 visited가 필요했을까 // 궁금증 2: bfs의 if 조건문에서 map이 1인 경우는 따져도 되지 않을까 #include #include #i..

주석 조건 참고 #include #include #include #include using namespace std; queue q; bool visited[100001] = { 0, }; void bfs(int n, int k) { q.push(make_pair(n, 0)); while (!q.empty()) { int value = q.front().first; int cnt = q.front().second; q.pop(); if (value == k) { cout > k; bfs(n, k); return 0; }

이번 문제는 DFS를 활용하여 풀려했었다. 하지만, DFS로 구현할 경우에는 TLE가 발생한다. 게시판에서는 BFS를 활용하여 풀어야 한다고 조언한다. 문제를 풀 때 어떤 포인트에서 DFS 혹은 BFS로 풀어야 하는지 알 수 있을까? 여러 블로그를 읽어보다가 감이 잡힌 듯하다. 최단 경로를 알아보아야 할 때, BFS BFS는 어떤 기준점으로부터 인접한 노드들을 차근차근 접근 해나가지만 DFS는 한 군데 길로 쭉 갔다가 조건을 만족하지 못하면 다시 돌아와 다른 노드들을 접근하기 때문에 시간적인 측면에서 BFS가 이런 부분에서는 효율적이다. 하지만, 경로에 대해 가중치(weight)가 붙을 때는 DFS를 활용해야 한다. 이동 과정에 있어서 여러 제약이 있을 때는 DFS (이 점에서 백트래킹과 유사한 거 같다..