https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net BFS 문제다. 처음 떠올린 방법은 덩어리를 찾아 덩어리 별로 같은 숫자로 저장하는 것이다. 그 후 각 덩어리의 테두리로부터 본인 숫자보다 큰 덩어리에 닿는 경우의 수를 모두 찾은 후 최솟값을 출력하는 것이다. 시간이 오래 걸릴 것 같아 최대한 반복을 덜 돌리려고 고민을 했다. 모든 경우의 수를 찾지 않고, 다리의 최소 길이보다 이동 수가 많아지면 함수를 바로 종료하는 것이다. 그리고 테두리를 따로 구..
BFS
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net BFS 문제다. 문제 이해에 이틀을 쓴 것 같다...ㅋ 불도 사람처럼 1분에 한 칸만 움직이는 줄 알았는데 불은 1분에 4방향으로 다 퍼지는 것이었다. 이 부분을 해결하고 나니 첫 번째 의문은 해결됐고 다른 의문이 생겼다. 몇 분이 걸리는지가 중요한 문제이기 때문에 한 타임에 딱 한 번만 움직여야 하는데 그 부분 구현이 의문이었다. 나는 큐의 사이즈를 구한 후 그만큼만 돌리면 된다고..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS와 구현이 함께 있는 문제다. 문제의 알고리즘 분류를 보니 DFS로도 풀 수 있는 것 같다. 그림 문제처럼 덩어리를 파악하고 치즈 문제처럼 배열 전체에 BFS를 적용하는 횟수를 구해야 한다고 생각했다. 경험이 있는 문제들의 응용 문제 같아서 알고리즘이 쉽게 떠올랐다. 이 문제의 주의점은 올해(?) 녹은 빙산이 0이 되어 다른 빙산에 영향을 주면 안된다는 것이다. 이걸 해결하기 위해서는 ..
https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net BFS 문제다. 배열의 한 칸을 기준으로 움직이는 것이 아닌 직사각형 묶음으로 움직이는 것이다. 움직이는 방향의 변의 길이만큼 확인을 해야 한다. 예를 들어 우측 방향으로 이동을 해야 한다면 별로 표시된 부분이 벽인지 혹은 범위를 벗어나는지 검사해야 한다. 직 사 * 각 형 * 처음에는 dx, dy 배열을 사용하지 않고 상하좌우를 각각 나눠 검사하고 큐에 넣었다. 검사하는..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net BFS와 구현이 함께 있는 문제다. 인접한 국가의 인원수가 조건을 만족하면 하나의 영역으로 묶되, 그 국가들을 모두 기록해둬야 한다는 점이 복잡하게 만들었다. 효율적인 방법을 찾다가 그냥 큐 하나를 더 만들었다...^^ 인접한 국가 덩어리를 모두 찾은 뒤 해당 국가들의 인원 수를 변경해주는 작업을 계속해줘야 해서 반복문을 많이 이용했다. 더 이상 국경선이 열리지 않을때까지 반복하고 ..
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net BFS와 구현이 함께 있는 문제다. 이 문제의 핵심은 치즈 안에 있는 공간을 어떻게 처리하느냐다. 처음에는 문제 파악을 제대로 하지 못하고 모든 0에 대하여 BFS를 진행했다. 이게 아님을 깨닫고... 치즈 속 공간을 어떻게 처리해야 하나 계속 고민했는데 혼자 깨닫기는 실패 구글링으로 힌트를 얻었다. 나는 치즈를 BFS로 처리하려고만 했지 공기를 BFS로 처리하는 것은 생각도 못 했다. 이것이 해결 방안이었다. 테두..
