DFS

문제 링크 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이번 문제는 이전 벽 부수고 이동하기 시리즈 1~3과는 조금 다릅니다. 이전 문제들은 벽을 부수고 지나가면서 최단 경로를 구하는 문제였지만, 이번 4번째 문제는 벽을 부수고 이동할 수 있는 칸의 개수를 세어보는 경우의 수 문제로 바뀌었습니다. 이번 문제는 풀면서 저도 우여곡절이 살짝 있었기에, 그런 우여곡절들을 공유하면서 풀이해보겠습니다. 풀이 DFS로 풀이했습니다. (BFS도 가능) 보통 경우의 수는 백트래킹으로 풀이하는데, 백트..

문제 링크 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 요즘들어 또 비가 주륵주륵 내리기 시작합니다... 여름이 다 가고 있기도 하구요. 이럴 때일수록 감기에 조심해야 됩니다! 이 글을 보는 모든 분들 환절기에 감기 안걸리고 건강하시길 기원하겠습니다! 🙋‍♂️ 이전 글에 이어서 트리 관련 문제를 풀어보겠습니다~ 풀이 DFS로 풀이하면 됩니다. (문제의 숨겨진(?) 트릭을 발견하면 쉽습니다) 문제에서 백트래킹에 의한 중위순회를 그림으로 보여주고 있습니다. 그러고나서 순회의 횟수를 세라고 하고 있습니다. 하지..

문제 링크 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 요새 트리를 많이 접하지 않고, 그래프만 접하고 있는 것 같아 오늘부터 트리 연습을 하기로 했습니다! 🌲 오늘도 열심히 문제를 풀어봅시다~ 풀이 문제에서 주어진대로 구현(재귀)하거나, DFS로 풀으면 됩니다. 저는 문제에서 주어진대로 노드를 삭제하고, 리프 노드의 개수를 셌습니다. 문제에서 제시하는 풀이는 어렵지 않지만, 예외처리를 하는데 조금 번거로움이 있었습니다. 백준 질문 게시판을 참고한 반례를 통해 알아낸 몇 가지 예외와 푸는 데 도움이 ..

문제 링크 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 그리디 문제집의 문제들을 살펴보다가, 재밌어 보이는 문제가 있어서 풀어보게 됐습니다. 처음에는 BFS로 풀면 되겠지하고 BFS로 풀어봤는데 모든 경우의 수를 탐색하는 것은 아니어서 틀렸습니다. 질문 게시판을 참고하니 DFS로 풀었다는 글이 다수여서 DFS로 풀었더니 시간초과가 발생했고, vst 배열로 오른쪽 끝까지 갈 수 없는 길을 다시 가지 않도록 최적화했더니 겨우 통과가 되었습니다. 배낭문제같은 그리디 문제만 접하다가 이런 DFS를 활용한 그리디 문제를 접하게 되..