deulee의 개발 노트

문제 N•M의 모눈종이 위에 아주 얇은 치즈가 다음과 같이 표시되어 있다. 회색 부분은 치즈를 나타내고 흰색 부분은 공기를 나타낸다. 이때 다음처럼 치즈 밖에 있는 공기를 외부 공기, 치즈 안에 있는 공기를 내부 공기라고 할 수 있다. 치즈는 외부 공기에 두 변 이상 만나게 되면 1시간 뒤에 사라진다. 그럼 모든 치즈가 다 녹게 되는데 몇 시간이 걸리게 될까? 이때 모눈정이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M이 주어진다. (5 ≤ N, M ≤ 100) 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 예제 입력 8 9 0 0 0 0 0 0 0 0 0 ..

알고리즘/문제 2023. 6. 4. 22:55

문제 N•M의 행렬로 표현되는 맵이 주어진다. 맵은 0과 1로 이루어져 있으며 '0'은 이동할 수 있는 곳 '1'은 벽을 의미한다. (0, 0)부터 시작하여 (N-1, M-1)의 위치까지 이동하는 최단 거리를 구해야 한다. 이때 상하좌우로 이동할 수 있으며, 벽은 한 개까지 부수며 이동할 수 있다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 1,000) (1 ≤ M ≤ 1,000) 다음 줄에는 N개의 줄에 M개의 숫자가 주어진다. 예제 입력 6 4 0100 1110 1000 0000 0111 0000 예제 출력 15 문제 해결 어디서 힌트를 얻을 수 있을까? '행렬', '최단 경로'를 통해 이 문제가 BFS를 이용하여 문제를 풀 수 있다는 것을 알 수 있다. 우선 최단 경로란 한 번 방문한 노..

알고리즘/문제 2023. 5. 25. 23:14

BFS는 가중치가 있는 간선이 있는 그래프에서는 최단 거리 알고리즘으로써 사용될 수 없다. 그 이유는 BFS는 방문한 순서대로 동작을 하게 되기 때문이다. 그렇기 때문에 다음과 같은 상황에서 전혀 사용할 수 없는 것이다. 시작점이 A라고 가정해보자. 시작점 A를 방문하게 되었을 때 BFS 알고리즘을 이용하게 된다면 (2, B)와 (12, C)를 '그냥 큐'에 넣게 될 것이다. 그리고 나서 D를 방문하게 되고 알고리즘은 종료를 하게 될 것이다. 이렇게 될 경우 BFS 알고리즘 입장에서 A에서 C까지의 최단 경로가 12가 되는 것이다. 실제로는 2 + 4 + 3 = 9 인데도 말이다. 즉, A에서 C까지의 최단 경로는 A to C가 아니라 A to B to D to C가 되는 것이다. 이러한 상황에서 BFS..

알고리즘/이론 2023. 5. 21. 20:20