문제: www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제풀이 BFS로 주변 바다 블록의 개수를 세어서 바다 블록의 수만큼 현재 높이에서 뺀 후 board에 갱신하는 방식으로 문제를 풀었다. 처음 풀 땐 빙하의 최대 높이가 10이기 때문에 10년안에 모든 빙하가 녹을 것이라고 생각해서 1~10년을 brute-force 했었다. 하지만 다음 그림과 같은 반례가 있기 때문에 빙하가 녹는 기간은 10년을 훌쩍 넘을 수 있다. 때문에 빙하가 두 덩이가 되거나..

문제: www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 문제풀이 BFS를 이용해 최단거리를 구하는 문제이다. 불과 상근이의 시작점을 큐에 넣어 BFS 하면 상근이는 먼저 붙어있는 불을 피해 이동할 수 있게 된다. 이때 상근이를 큐의 마지막에 넣어야 불과 상근이가 같은 장소로 동시에 이동하는 일이 없다. 코드 #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,..

문제: www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제풀이 BFS 알고리즘 문제이다. 큐와 방문여부배열, 영역개수를 2개씩 선언하여 하나는 색약이 아닌 사람 다른 하나는 색약인 사람의 영역 개수를 구하였다. 코드 #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int visited1[100][100] = {0..

문제: www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제풀이 브루트포스와 BFS 알고리즘을 이용하여 문제를 풀었다. 비의 높이(h)에 대하여 h보다 높이가 높은 지대의 인접한 땅들의 영역 개수를 BFS로 구한다. 이때 h가 0부터 100일 때까지의 경우의 수 모두 비교한다. 코드 #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int board[100][1..

문제: www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제풀이 각 영역의 넓이를 구하여 오름차순으로 출력하는 문제이다. BFS를 이용하여 각 구역에 대하여 탐색하고 그 넓이를 각각 벡터에 저장하였다. 벡터를 sort() 함수를 이용해 오름차순 정렬시킨 후 출력하였다. 코드 #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; ..

문제: www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제풀이 BFS를 이용하여 최단거리를 구하는 문제이다. 다른 너비우선탐색과 다르게 dx, dy가 상하좌우가 아닌 나이트 말이 움직일 수 있는 수로 고쳐주면 된다. int dx[4] = {-1,1,0,0} --> int dx[8] = {-2,-2,-1,-1,1,1,2,2} int dy[4] = {0,0,-1,1} --> int dy[8] = {-1,1,-2,2,-2,2,-1,1} 코드 #include #in..