한 주 동안 해결한 알고리즘 문제들중에서 몇몇 문제에 대해서 배운 점이나 주의해야할 점을 기록하겠습니다.
(모두 백준에서 알고리즘 문제를 풀었습니다.)
📌 7569번 토마토 - 🏅Gold Ⅴ
이런 비슷한 류의 문제를 풀어봤기 때문에 풀 수 있었던 것 같습니다. 아마 모르는 상태로 이 문제를 풀었다면 못 풀었을 것 같습니다.
이 문제는 익은 토마토를 기준으로 안 익은 토마토가 영향을 받아 익게 되는 점(확산) 때문에 BFS를 떠올릴 수 있습니다.
그렇기 때문에 토마토들의 상태를 입력받을 때, 익은 토마토의 좌표를 미리 Queue에 저장합니다.
주의해야할 점은 격자모양 상자 하나 안에 여러 개의 토마토가 담길 것인데, 이 상자가 여러 개 쌓일 수 있기 때문에 x축, y축 뿐만 아니라 z축 까지 고려하여 탐색을 해야 합니다.
또한, BFS를 통해 익은 토마토를 기준으로 주변에 안 익은 토마토를 익게 하면서, 이전에 있던 좌표 값에서 +1을 하면서 몇 일 걸리는지 계산합니다.
모든 과정이 끝나면, 상자안에 토마토가 안 익은게 있는지 전부 탐색합니다.
📌 1780번 - 종이의 개수 🥈 Silver Ⅱ
재귀에 익숙치 않아서 생각하기 힘들었던 문제였습니다.
먼저, 한 size안에 같은 숫자(-1, 0, 1)만 있는지 체크할 필요가 있습니다. 같은 숫자면 그대로 그 숫자들의 개수를 count만 해주면 됩니다.
그게 아니면 종이를 9등분 해야하기 때문에 size를 3으로 나눠야 합니다.
9등분 된 종이를 같은 숫자만 존재하는지 확인하기 위해 재귀 호출을 합니다.
여기서 배운점은 3으로 나눈 size를 잘 응용해서 재귀 호출하여 탐색할 때마다 시작하는 인덱스를 정해주면 된다는 것을 배웠습니다.
📌 1520번 - 내리막길 🏅 Gold Ⅲ
이 문제는 DFS와 DP를 응용한 문제입니다.
어떻게 보면 기본적인 DFS를 구현할 때 큰 틀은 비슷합니다. 여기에 DP의 메모이제이션을 사용하여 현재 까지의 경로의 수를 저장해야 합니다.
메모이제이션을 사용하지 않고 그냥
DFS를 사용하게 되면 시간초과 발생
먼저, DP를 위한 배열을 모두 -1로 초기화해야 할 필요가 있습니다. 이는 어찌보면 방문 처리와 비슷한 역할을 합니다.(-1은 아직 방문하지 않은 칸입니다.)
중요한 점은 시작점에서부터 끝점까지 DFS 탐색을 하는건 똑같지만 이미 탐색해서 경로의 개수가 파악된 지점을 또 탐색하게 되면, 저장된 경로의 개수를 반환하면 됩니다.
왜 이렇게 하나면, 특정 지점에서 끝 점까지 경로의 개수가 저장되지 않았다면 끝 점까지 경로를 구하는데, 경로의 개수를 중복해서 세야하기 때문입니다.
그래서, 끝 점까지 탐색이 완료되면 DP를 사용하여 경로의 개수를 저장하고 다른 지점에서 또 탐색됐을 때는 이 경로를 더해주는 방식으로 구현해야 합니다.
📌 2146번 - 다리 만들기 🏅 Gold Ⅲ
이 문제에서 육지와 바다가 존재하는데, 이 육지를 구분해야할 필요가 있습니다.
예를 들어, 어떤 육지는 숫자 2로, 또 다른 육지는 숫자 3으로 변환하여 저장하는 것입니다.
왜냐하면, 육지와 육지 사이에 다리를 만드려고 코드를 구현하려고 하는데, 어떤 한 육지에서 계속 탐색하다가 바다를 건너 다른 육지까지 이동했는데, 이게 다른 육지인지 코드상에서 구분할 수 없기 때문입니다.
그래서 각각 육지를 나눴을 때, 이 문제를 수월하게 해결할 수 있습니다.
그리고, 이 구분된 육지를 가지고 BFS 탐색을 합니다.
이동하려는 위치가 바다면, 이동하려는 좌표와 다리의 개수를 +1해서 Queue에 저장합니다.
이런 식으로 과정이 진행되다가 이동하려고 하는 위치가 바다도 아니고 현재 육지와 다르다면 다리의 개수를 반환하도록 합니다.
