www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 처음 문제를 봤을 때 맵의 크기가 1500*1500 이길래 BFS두 개를 배열 초기화를 해가면서 사용해도 1초 안에 돌아갈까? 생각해서 구현해봤지만 TLE가 났다. 정 모르겠어서 찾아봤는데 물에 대해서 큐에 집어 넣어주고, nextQ에 넣어준 뒤에 Q = nextQ 를 통해서 복사가 가능했다..! 그리고 백조에 대해서 BFS를 해줘야 하는데 중간에 다른 백조가 있다면 BFS의 반환 값을 참으로 반환해준..

www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 탐색 + 구현 문제였다. 고슴도치는 물이 들어올 곳에 갈 수 없다는 말에 처음에는 bfs 한 번에서 고슴도치와 물을 전부 pop 해가면서 했는데 그러한 접근은 while문이 한번 돌 때마다 하나씩 pop 되기 때문에 실패했다. 다시 생각해봤는데 물의 위치에서 BFS한 것과 고슴도치 위치에서 BFS 한 것을 통해서 고슴도치가 갈 위치 + 1 < 물이 들어올 위치값 을 만족한다면 고슴도치가 갈 수 있겠다는 생각이 들어서..

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 끔찍한 구현 문제였다. 어떻게 구현해야 할지 생각이 안 나서 다른 풀이를 참고했는데 pair 객체를 통해 정렬해주면 쉽게 풀리는데 잘 익혀둬야겠다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가..

www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 빙하가 2차원 배열로 주어지는데 빙하 상하좌우에 0이 있다면 빙하가 0 하나당 -1씩 줄어든다. 구현하면서 신경 쓸만한 부분은 날짜가 지남에 따라 빙하가 녹는 것, 빙하로 이루는 땅이 2개 이상인지 확인할 것 2개만 신경써주면 된다. if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--; else if (!vis[nx][ny]) { q.push({ n..

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net BFS + 다익스트라 조합으로 풀면 된다. 기존 다익스트라는 1차원 배열에서 각 정점의 최단거리를 구했지만 이 문제에서는 2차원 배열로 선언해서 각 구간에 가기 위해서 우선순위 큐를 사용해서 최단거리로 갱신하며 이동한다. #include #include #include using namespace std; const int inf = 1e9; int ar[126][126], n; bool vi..

www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라와 BFS를 활용한 최단거리 찾기 문제였다. 이 문제는 다익스트라를 처음 배우고 풀어보려 했었는데 도저히 어떻게 풀어야 할지 몰라서 포기했는데 다익스트라를 좀 더 이해하고 보니 어떻게 활용해야 풀 수 있을지 알았다. 기존 다익스트라는 일차원 배열을 통해 한 노드에서 다른 모든 노드를 가는 최단거리를 구하지만 이번 문제에선 2차원 배열을 통해 각 배열의 최단거리를 구해준다. 입력은 ..