문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net BFS + 구현 문제이다. 삼성 기출 문제라고 하는데 나한테는 같은 티어의 골드4~5문제보다 어려웠다. 단순하게 생각했으면 쉽게 풀었을 것 같은데 너무 어렵게 생각하고 이 문제에 접근해서 그런 것 같다. 풀이 문제의 조건에 따라 BFS를 구현해주었다. 이때 고려할 것은 두가지이다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을..
문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 백준에 있는 불! 문제랑 비슷하다. 물에 대한 BFS와 비버에 대한 BFS를 각각 돌려주어 풀었다. 먼저 물에 대한 BFS를 돌아 물이 차는 시간과 방문 여부를 체크해주었다. 이후에 비버에 대한 BFS를 돌며 비버가 도착할 시간이 물이 차는 시간보다 작아야만 비버가 움직일 수 있기 때문에 조건을 달아주어 만족하는 경우에만 비버가 방문할 수 있게하는 것이 핵심이다. 하지만 예외상황이 발생할 수 있다...
문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 이 문제는 치즈 문제와 다르게 내부 공기/외부 공기의 구분이 없고, 영역의 개수를 구해야하기 때문에 모든 좌표에 대해 BFS를 돌아줘야한다. board의 값이 0인(바다)인 곳에 대해 모두 탐색을 하여 빙산이 있는 곳을 만나면 빙산의 높이를 하나씩 감소시켜주었고, 빙산의 높이가 0이 되면 방문처리를 해주어 이번 탐색에 녹아버린 좌표에 대해서는 BFS를 막아주고 최종적으로 현재 영역..
문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 골드5 치즈 문제를 풀고 이 문제를 접했다면 쉽게 풀 수 있었을 것이다. 이 치즈 문제는 골드5 치즈 문제와 다르게 치즈에서 각 치즈 격자의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것을 찾아내 녹여줘야하기 때문에 checkboard라는 2차원 배열을 새로 만들어 실내온도의 공기와 접촉한 변의 개수를 저장해주었다. 탐색을 하다가 치즈이면서, checkboar..
