https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 가로 세로가 50 이하이므로 브루트 포스를 더불어 사용했다. 육지(L)인 곳 중 상하좌우로 이어진 곳 중 최단 거리로 이동할 수 있어야 한다. 거리를 재기 위해 큐에서 카운트를 세어준다. 반환 값은 계산한 거리 중 가장 큰 값을 반환한다. 모든 행렬을 순환하면서 모든 육지(L)를 확인하며 최단 거리로 이동하는 시간을 갱신하여 출력한다. 📌CODE import s..
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 시작 층(S)에서 시작하여 도착 층(G)까지 U씩 올라가거나 D씩 내려가며 몇 번만에 다다를 수 있는지 판단해야 한다. 버튼을 누르는 횟수는 방문 배열을 사용하여 구하도록 했다. F층 이내에 있는 층 중 방문하지 않은 층을 방문하며 횟수를 세어준다. 도착 층(G)에 다다르면 방문 배열로 센 횟수에서 -1을 해서 출력한다. 첫 시작을 1로 했기 때문에 -1을 해줘야 함을 ..
https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 상하좌우로 연결된 부분을 하나의 그림으로 보고, 그림의 크기와 개수를 구해야 한다. 그림의 크기는 BFS를 수행하면서 연결된 곳이 있을 때 마다 개수를 세어주고, 그림의 개수는 BFS가 정상적으로 끝난 후 개수를 세어주면 된다. BFS 과정에서 별도의 방문 배열 없이 기존 입력받은 배열을 갱신해가며 그림이 있을 때(1) BFS를 수행하여 그림이 없다고(0) 변경한..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡IDEA BFS를 사용하여 구현하는 문제이다. 인구 이동 조건에 따라 구현하는 과정 중 인접한 나라 중 인구 차이가 L이상 R이하인 나라끼리 연합을 맺는다는 부분에서 BFS를 사용해야 한다. 상하좌우로 인접한 나라가 범위 내에 있고, 방문하지 않았고, 현재 나라와의 인구 차이가 L이상 R이하라면 큐에 추가해주는 식으로 구현했다. 이 때 연합한 나라들을 저장해두는 union 배열에도..
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 💡IDEA 문제의 조건대로 구현해야 한다. 네 개의 톱니바퀴를 어떤 방향으로 돌려야 하는지 알아야 하는데, 현재 바퀴와 맞닿은 바퀴들의 방향도 조정해주어야 한다. 이 과정에서 나는 BFS를 사용했다. 현재 바퀴의 번호를 바탕으로 인접한 바퀴의 맞닿은 부분이 같은지 다른지 판단하여야 한다. 왼쪽과 닿는 것은 현재 바퀴의 -2번째와 왼쪽 바퀴의 2번째이고, 오른쪽과 닿는 것은 현재 바퀴의 2번째..
https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 음식물이 있는 곳(1)과 없는 곳(0)을 구별하여 음식물이 있는 곳에서 BFS를 돌며 상하좌우로 연결된 음식물을 찾는다. 음식물을 찾으면 음식물이 없다고 갱신해주고, 개수를 센다. 이런식으로 하면 굳이 방문배열을 만들지 않고도 입력받은 맵 배열 하나로 해결된다. BFS를 돌면서 음식물이 없어지기 때문에, 음식물이 있는..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 자주 접했던 문제라 정말 금방 풀었다. 조금 다른 점은 방향이 8방향 인 점 정도이다. 모든 행열을 돌면서 섬이 있는 곳을 발견하면 거기서부터 갈 수 있는 모든 곳을 탐색하고 방문 기록을 한 후 돌아온다. BFS를 한 번 수행하는 게 한 번 카운트 하는 것이다. 방문 기록은 따로 배열을 만들기보다 기존에 받아온 이차원 배열에서 섬(1)인 곳을 바다(0)..
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 이 문제는 맥주를 50미터마다 하나씩, 20개씩 한 상자를 꾸준하게 마시고 편의점에서 채운다는 맥락에서 결국 1000미터 안에만 편의점이 있으면 된다는 것이 중요하다. 일반적인 BFS와 거의 유사하지만, 좌표 범위가 -32768 ≤ x, y ≤ 32767이므로 자주 사용하던 이차원 배열의 방문 확인용 배열을 만들기보다 그냥 방문한 좌표 자체를 저장하는 ..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 먼저 모눈종이의 사각형을 표시하기 위해 2차원 배열에 입력받은 사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표를 사용하여 사각형이 존재하는 부분은 1로, 그렇지 않은 부분은 0인 상태로 둔다. 모든 사각형을 표시했다면, 사각형이 없는(0) 지점을 찾아서 BFS를 수행하며 상하좌우로 연결된 영역의 넓이를 세며 방문 확인을 해준다. BFS를 수행한..
