Jumping to the water

▶ 문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ▶ 설명 단계별 문제풀기에서 바로 이전 문제인 토마토에서 변형된 문제이다. 왼쪽은 그림은 2차원 배열로 토마토 상태를 입력받아 아래, 위, 좌, 우를 탐색하여 방문했던 반면, 오른쪽 그림은 3차원 배열로 토마토 상태를 입력받은 다음 가로세로 방향으로 아래, 위, 좌, 우, 높이 방향으로 위,아래를 탐색해야 한다. 탐색할 곳의 방향의 수가 증가하여 4번 탐색에서 6번..

▶ 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ▶ 설명 토마토 상자에서 익은 토마토는 1, 익지 않은 토마토는 0, 토마가 아닌 곳은 -1으로 표시된다. 예제 3에서 익은 토마토는 2개이고, 익은 토마토에서 익지 않은 근접한 토마토로 1씩 방문 카운트를 증가시킨다. -1라고 되어 있는 곳은 토마토가 없으므로 방문을 하지 않는다. 처음 Queue에 저장되는 데이터 단계별로 풀어보기 문제 중에서 이전 문제였던 미로 탐색과..

▶ 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ▶ 설명 갈림길 없이 일직선으로 되어 있는 미로라면 DFS, BFS로 이동 거리를 구할 수 있지만 갈림길이 있는 미로라면 BFS로만 최소 이동 거리를 구할 수 있다. 문제의 예제를 살펴보면 1로 된 곳은 지나갈 수 있지만 0은 지나갈 수 없는 조건이 주어졌다. 그럼 출발선인 1,1부터 살펴보자. 내부적으로 2차 배열로 만들 것이기 때문에 처음 시작하는 곳은 0,0 라고 할 수 있다. 먼저, [0,0] 에서 갈 수 있는 ..

▶ 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ▶ 설명 단지번호 붙이기 문제와 아주 유사하다. 입력받는 방식이 다르고, 1끼리 인접해있는 곳의 개수를 구해주기만 하면 되겠다. 먼저, 배추가 있는 곳을 1, 없는 곳을 0으로 표시할 배추밭 2차원 배열을 구성한다. 2차원 배열을 초기화할 때 값이 모두 0이므로 이제 1인 곳만 알아내서 값을 주도록 하면 된다. 입력에서 1인 곳의 인덱스를 주고 있으므로 편하게 1을 배열에 저장할 수가 있다. 그렇게 ..

▶ 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ▶ 설명 1이 몇개씩 모여있는지 오름차순으로 출력하는 문제이다. 먼저, 2차 배열로 0과 1의 값을 입력 받는다. 이 2차 배열 요소를 모두 탐색하며 1인 곳에서 DFS혹은 BFS로 탐색을 이어나가고, 0인 곳은 그냥 지나가게 한다. DFS를 (혹은 BFS) 사용할 때 다음 노드로 탐색을 이어가기 위해서는 좌,우,위,아래의 위치를 통해 배열의 범위 밖을 넘어가는 위치, 혹은 원소 값이 0일..

▶ 문제 https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net ▶ 설명 이전 글에서 다뤘던 깊이 우선 탐색1 에서 정렬 조건만 달라진 변형된 문제이다. 예제를 그래프로 그리면 위와 같이 나타낼 수 있는데 노드마다 연결된 노드들을 나열하면 다음과 같다. 노드1 : 4, 2 노드2 : 1, 3, 4 노드3 : 2, 4 노드4 : 1, 2, 3 노드5 : x (연결된 노드 없음) 노..