BFS9 백준 알고리즘: 2636번 치즈 문제 정보 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 핵심 BFS(너비 우선 탐색)을 사용하여 문제를 풀이한다! 이를 사용하는 근거는, 치즈 조각은 한 시간이 지날때 마다 점차 녹아가며 우리가 구해야 하는 것은 모든 경로를 탐색하는 것이 아닌 각자의 위치(공기)에서 녹일 수 있는 치즈를 천천히 녹여가며 모든 치즈가 녹는 데에 걸린 시간과 한 시간 전에 남아있는 치즈 조각을 구하는 것이기 때문이다 사실상 이를 떠올리는 것은 어렵지는 않고, 좀 까다로웠던 것은 (0,0) 부터 맵을 탐색하기 시작하여 0(공기)이면 큐에 추가하고.. 알고리즘/Java 2023. 11. 22. 백준 알고리즘: 7576번 토마토 문제 정보 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 핵심 역시 이전 문제와 비슷한 BFS(너비 우선 탐색)을 활용하여 풀이하는 문제이다 이 문제에서 하루가 지나면 익은 토마토의 상하좌우의 익지 않은 토마토들은 익은 토마토로 변하게 되는데, 모든 익지 않은 토마토가 익은 토마토가 될 때까지의 최소 날짜를 출력하는 것이다 하지만, 1. 익지 않은 토마토(0)가 모두 익은 토마토(1)로 변했음을 어떻게 파악할지 2. 익은 토마토로 변했을때 최소 날짜는 어떻게 카운팅하는 것이 좋을지 이 두가지.. 알고리즘/Java 2023. 11. 14. 백준 알고리즘: 2206번 벽 부수고 이동하기 문제 정보 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 핵심 얼마나 효율적으로 케이스를 분리해서 문제를 풀이하는가.. 가 중요한 것 같다 (모든 문제가 그렇지만) 이 문제는 BFS(너비 우선 탐색)을 활용하여 풀이하는 문제이며 모든 경우의 수를 확인해야 하는 문제가 아니고 최단 거리를 구하는 문제이기 때문에 DFS는 적합하지 않을 것 같다는 판단을 하였다 중간에 막혔던 부분이 있고, 그 부분을 해결해 나갔던 과정과 함께 풀이를 해보도록 하겠다 살짝 소개하자면, 벽은 반드시 한 개만.. 알고리즘/Java 2023. 11. 13. 백준 알고리즘 1260번: DFS와 BFS 문제 정보 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 핵심 DFS와 BFS에 대해서 알고 있는지? 그래프를 탐색하는 알고리즘에 대한 지식을 가지고 있는지? 그들을 어떤 Data Structure를 통해 구현해야 하는지 알고 있는지? 개인적으로 내부 알고리즘에서 중요한 요소는 이렇게 된다고 생각한다 - 해당 노드를 방문했는지 확인하는 boolean visitied[] - 노드들 사이 간선을 판단하는 boolean edge[][] - BFS의 경우 FIFO를 가능케 하는.. 알고리즘/Java 2023. 9. 19. 이전 1 2 다음
