https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1. 입력받을 때, 9가 나오면 상어의 위치이므로 기록해둔다. 2. 다른 물고기들의 개수를 세서 물고기가 오직 한마리면 바로 거리를 계산하고 종료! -> (x좌표의 차 + y좌표의 차) = 거리 3. 만약 물고기가 여러 마리일 경우, bfs()를 반복실행! ※ 반복실행하는 이유 : 상어가 가장 가까운 먹이를 찾아서 그것을 먹을 때 마다, 다른 먹이들과의 최단거리가 바뀌기 때문에 다시 게산..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 이 문제는 bfs에 구현을 섞은 문제이다. 총 3가지의 주요 로직으로 이루어져 있다. 1. 가장자리 입력부터 차근차근히 보자면, 입력을 받을 때 0행, 마지막 행, 첫 열, 마지막 열은 가장자리로써 상근이가 자유로이 접근할 수 있기 때문에 모두 큐에 넣어주자. 그러나! 가장자리에는 벽이 올 수도 있고, 문 또는 키, 그리고 빈칸 모두가 올 수 있다. 그러므로 입력을 받을 때 이들을 걸러주자. case1...
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 단순 bfs문제 + 벽을 한번 부술 수 있다는 특징이 있는 문제이다. 주요 풀이는 다음과 같다. 3차원 배열을 선언하여 거리를 저장해주는데 벽을 부수고 이동하면 [x][y][0] 에 값을 저장해주고 벽을 안부수고 이동했다면 [x][y][1]에 값을 저장해준다. 다음 이동할 좌표가 맵의 범위 안이라면, 2가지 경우로 나눈다. 1. 벽을 만났는데, 뚫을 수 ..
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 얼핏보면 까다로운 문제처럼 보일 수 있지만, 이 문제의 키포인트는 치즈의 외부 공기와 내부 공기를 잘 구분하면 된다! 그렇게 할 수만 있다면 외부 공기와 2면 이상 닿은, 즉 곧 녹을 치즈를 구하는 건 어렵지 않다. 그렇다면 어떻게 외부 공기와 내부 공기를 구분할까? 가장자리에는 치즈가 올 수 없다고 하였으므로, (0,0)에서 부터 bfs를 시작한다. 0,0에서 bfs를 통해 갈 ..
https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 이 문제는 bfs 기본코드에서 약간의 응용이 필요하다. 우선 갈 수 있는 방향이 1.상 2.하 3.좌 4.우 5.좌상 6.우상 7.좌하 8.우하 9.제자리 로 총 9가지다. 그리고 벽이 1초에 한 줄씩 내려온다고 하였으므로, 1초마다 벽의 위치를 움직여줘야한다. 0,0에서 부터 for문을 시작하면 벽을 내리고, 내린 벽과 기존 벽을 구분하기 어려우므로 밑에서부터 for문을 시작하여 ..
https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만-포드 알고리즘을 사용하는 문제이다. 그래프에서 음의 가중치가 등장한다면, 다익스트라로 해결할 수 없으므로 벨만-포드 알고리즘을 적용하자. 벨만 포드 알고리즘이란? 그래프의 최소비용을 구하는 알고리즘 중 하나로, "모든 경우의 수를 전부 탐색하여 최소비용을 찾는다." 자세히 말하자면, N개의 정점이 존재할 때 N-1번 탐색해야한..
