https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 우선 입력을 받고, 빨간 구슬의 위치와 파란 구슬의 위치를 구조체를 하나 만들어서 동시에 관리해준다. 큐에 담겨있는 정보를 가져와 4방향에 대해 탐색을 하는데, 벽을 만나거나 탐색한 곳이 구멍이 아닐 때까지 while문을 통해서 쭈욱 직진한다. (이 개념이 이해가 되지 않는다면 백준 레이저 통신 문제를 풀어보시길..!) 판을 한 방향으로 기울여 볼..
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문을 시작하여 ..
