https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net BFS 문제다. 배열의 한 칸을 기준으로 움직이는 것이 아닌 직사각형 묶음으로 움직이는 것이다. 움직이는 방향의 변의 길이만큼 확인을 해야 한다. 예를 들어 우측 방향으로 이동을 해야 한다면 별로 표시된 부분이 벽인지 혹은 범위를 벗어나는지 검사해야 한다. 직 사 * 각 형 * 처음에는 dx, dy 배열을 사용하지 않고 상하좌우를 각각 나눠 검사하고 큐에 넣었다. 검사하는..
Algorithm
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 탐색을 좌..
