Jumping to the water

▶ 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net ▶ 설명 3차 배열 사용 미로탐색, 토마토 문제와 같이 BFS로 풀 때 2차 배열을 Queue에 저장/삭제하며 노드를 방문하는 방식을 사용했다. 하지만 이번 문제는 2차 배열로 풀기엔 적합하지 않았다. 벽을 부술 때 체크하는 boolean 체크 배열을 따로 만들기도 해보고, 2차 배열이 아닌 ArrayList를 사용해보기도 했지만 메모리초과가 거듭 발생하기만 했다..

▶ 문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net ▶ 설명 10x10 로 된 보드가 있다. 주사위를 던져 나오는 숫자대로 이동을 할 때 사다리가 나오면 사다리가 인도하는 곳으로 (앞으로) 전진하고, 반대로 뱀이 나오면 후퇴하여야 한다. 예제 1을 살펴보면 3개의 사다리와 7개의 뱀이 주어졌다. 보드판의 숫자를 1차 배열로 만들기 사다리와 뱀 게임 보드판을 표 형식으로 그려보았다. 예제의 입력..

▶ 문제 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을 배열에 저장할 수가 있다. 그렇게 ..