1. 문제 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 2. 풀이 백준 실버 1의 DFS 문제이다. 첫 번째 줄의 입력을 받아 R, C를 초기화하고 map 선언한 후 마당의 각 줄의 정보를 입력받아 배열을 초기화한다. 그 후 방문 배열을 선언 및 초기화하고 한 칸에서 수평, 수직으로만 이동할 수 있다고 제시했으므로 행과 열은 1씩 이동이 가능하다는 이야기 이다. 따라서 이동할 좌표를 선택할 수 있는 dx, dy 배열도 그에 맞게..
1. 문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 2. 풀이 입력으로 주어지는 L (땅)에서 보물이 있을만한 곳을 탐색하기에, 하나씩 BFS로 탐색하면서 보물이 있는 곳을 찾아야한다. 보물이 있는 곳을 찾았다면 BFS로 탐색하기 때문에 탐색할 때마다 거리를 계산한다면 자동으로 최단거리가 된다. 3. 소스코드 import java.io.*; import java.util.*; public class Main { static int N, M;..
1. 문제 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 2. 풀이 백준에서 탐색 문제로 분류되어 있다. BFS, DFS의 개념을 알고 있다면 크게 어려울 것이 없는 문제였다. 핵심은 음식물 쓰레기가 있는 지점부터 시작하여 탐색을 진행하는데, 상하좌우에 쓰레기가 있으면 하나의 쓰레기 묶음으로 처리되므로, 다음 번을 탐색할 때 음식물 쓰레기가 있는지를 판단해주어 탐색을 하면 충분히 해결된다. 3. 소스 ..
1. 문제 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 2. 풀이 BFS 문제이다. 처음 문제를 읽고, 예제 입력을 봤을 때는 무슨 말인지 이해가 안됬지만, 예제를 하나씩 따라가다 보면 충분히 이해할 수 있는 문제였다. 우선 점의 x, y 좌표와 그 점까지의 거리값을 넣을 static class를 하나 선언해준다. 그 다음 입력을 받고 점들을 반복문으로 탐색하면서 1이 아닌 0인 점부터 bfs 탐색을 시작한다. ..
1. 문제 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 2. 풀이 DFS로 문제를 해결하였다. 주어진 1과 0을 2차원 배열에 넣었다고 가정한다면 문제에서 말하는 가장 바깥쪽은 배열의 첫번째 행, 가장 안쪽은 배열의 마지막 행이된다. DFS를 돌릴 때 Main 함수에서 배열의 첫 번째 행을 반복으로 돌리면서 DFS를 탐색해주고 DFS 함수 안에서 탐색을 진행하던 도중 인자로 받은 x 값이 마지막 행에 도착..
1. 문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 2. 풀이 생각보다 삽질을 많이 한 문제였다. 처음에는 '빗물의 높이를 모르는데 어떻게 구하지?'라고 생각했는데 문제를 다시 잘 읽어보니 '비의 양에 따른 모든 경우를 다 조사해보면'이라는 문구를 보고 브루트포스를 떠올렸고 탐색을 하며 최대 개수를 구하는 문제니 DFS나 BFS를 생각했다. 여기서는 DFS로 문제를 해결하였다. 브루트포스를 돌릴 때 주의해야할 점은 노트에 적혀있는대로 '아무 ..
1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 풀이 깊이 우선 탐색(DFS)의 응용이다. 큰 응용이 아니라 정답 비율이 높은 것 같다. DFS의 기본적인 내용은 아래의 포스팅을 참고하면 많은 도움이 된다. https://velog.io/@songyw0517/DFS%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80 DFS란 무엇인가? 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 ..
