전체 글

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로 처리하는 것은 생각도 못 했다. 이것이 해결 방안이었다. 테두..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net BFS 문제다. 전염은 BFS로 풀면 간단할 것 같았는데 우선순위를 어떻게 처리해야 할 지 난감했다. 바이러스 번호, x, y를 하나로 묶어서 정렬을 해야하나 했는데 초마다 정렬해야 할 것 같아서 패스 초만큼 반복을 하고 그 안에서 배열을 계속 반복하며 1일 때만 전염, 그 후 2일 때만 전염으로 하려다가 이것만큼 비효율적인 방법이 없을 것 같아 패스... 총 두 가..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net BFS 문제다. BFS에 익숙한 편은 아니라서 정보 없이 문제를 접했다면 BFS를 떠올리지 못했을 것 같다. (BFS 문제임을 알고도 BFS보다 노가다로 구현하려고 했으니까...) 2차원 배열이 아니라는 점도 BFS로 떠올리지 못한 이유 같다. 1차원 배열에서는 앞뒤로 움직이는 두 가지 경우만 고려해주면 된다. 배열에 대한 정보가 입력되는 것이 아니기 때문에 board 배열은 사용하지 않았다. visit 배열..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net BFS 문제다. 이어져 있는 1들을 찾기 위해서는 BFS, 연속된 1이 몇 묶음(?) 있는지 알기 위해서는 단순하게 부르트포스를 이용했다. 보통 BFS를 사용할 때는 board 배열, visit 배열 두 개 를 사용한다. 이 문제에서는 입력이 0과 1만 들어오고, 원본을 유지해야 할 필요가 없으므로 visit 배열을 선언하지 않고 board배열의 값을 바꿔주었다. (방문 시 1을 0으로) 1 탐색을 좌..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 구현 문제다. 블록이 높이 쌓인 곳을 찾는 게 우선이라고 생각했다. 1. 처음 생각한 방법은 첫 줄을 기준으로 잡고 기준 보다 더 큰 지점을 찾아가는 것이었다. 큰 지점을 찾기까지 기준의 높이와 해당 줄의 높이 차를 합산하는 방법을 생각했다. 그러나 끝 줄이 항상 높지 않고 그러면 전 기준까지의 합산을 되돌려야 하기 때문에 비효율적이라 생각했다. 이 방법을 패스하고 다른 방법을 ..