두부의 코딩일기

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 위 문제는 dfs와 bfs를 이용해서 풀 수 있는 것처럼 보이지만 dp를 이용하지않으면 시간초과가 발생한다. 메모제이션, 즉 dp를 이용해서 실행시간을 단축시켜야한다. 출발지가 정확하게 명시되어 있지 않은 문제이기 때문에 bfs를 이용해야하고, 메모제이션을 이용해서 해당 과정에서의 시간을 단축시키면 된다. 우선 2차원 배열을 생성하고 임의의 출발지에서 상하좌우로 움직이면서 최대한 ..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 인접해있는 땅과의 인구수 차이가 L과 R 사이이면 국경선이 열리고 연합 내의 동일한 인구수를 가진다. 위 문제는 bfs, dfs 아무거나 사용해도 무관하기 때문에 본인이 원하는 걸 사용하면 된다. 필자는 bfs를 이용해서 문제를 풀었다. while (true) { visited = new boolean[N][N]; // 방문 유부 isMove = false; // 변경 유무 f..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 이번 문제는 bfs와 dfs를 동시에 사용하는 문제로 3개의 벽을 세워서 바이러스로 부터 안전한 구역을 최대한 넓게 만들어야한다. 우선 임의로 중복되지 않은 3개의 벽을 계속 세워야하므로 dfs를 이용한다. 벽을 세우고, 다시 복구를 반복하면서 벽 3개가 완성되면 bfs를 돌리면 된다. public static void dfs(int wall) { if (wall == 3) { bfs(); // 벽이 3..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 조건이 많아서 생각할 게 많았던 bfs 문제로 알고리즘 진행 과정을 보면서 설명하겠다. 1. 입력받은 값 중에 '9'는 아기 상어의 위치이며 아기 상어는 총 1마리만 존재한다. 1) 아기 상어의 x, y 좌표를 저장함 (shark_x, shark_y) 2) 저장 후에 아기 상어의 위치는 0으로 변경한다. (해당 위치도 탐색 과정에 포함되어야함) 3) 물고기 위치를 담을 수 있는 배열 ..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import java.io.*; import java.util.*; public class Main { static int[][] node; static boolean[][] visited; static int N; static String result_dfs = ""; static String result_bfs = ""; public static void ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 이 문제는 dp를 사용하지 않고 bfs와 dfs를 사용하게 되면 메모리 초과가 발생한다. 그렇다면 dp를 활용해서 메모이제이션을 해주어야한다. 예제 1번에서 2, 3번째 방법을 그림으로 보면 메모이제이션을 쉽게 이해할 수 있다. 그림을 보면 알 수 있듯이 20부터 도착지까지 갈 수 있는 방법이 동일하다. 그렇기 때문에 왼쪽 그림처럼 먼저 dfs 탐색을 진행했다면 오른쪽 그림의 경로에선 20..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 해당 문제는 dfs, bfs 어떤 방법을 사용하던지 풀리는 문제인데 필자는 bfs를 이용해서 풀었다. 서로 연결된 컴퓨터를 저장하기 위해 int형 배열 map을 생성해주고, 해당 배열에 map[출발지][도착지] = 1, map[도착지][출발지] = 1을 입력해준다. for (int i=0; i

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 최근에 풀었던 미로탐색(2178번), 숨바꼭질(1697번) 문제와 동일한 유형이다. 이 문제를 풀어보기 전에 먼저 풀어보는 걸 추천한다. 위 문제를 풀었으면 bfs 방법에 대해서는 확실히 이해했다고 가정하고 간단하게 설명하겠다. 이번 문제는 익은 토마토를 기준으로 상하좌우 한 칸씩 모든 토마토를 익혀야하는 문제이다. 즉, bfs를 중간에 끊지말고 끝까지 돌려야한다는 의미이다...

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해당 문제는 (0, 0)에서 출발해서 (N, M)까지 최단 경로를 구하는 bfs 문제이다. 서로 인접한 칸만 이동할 수 있으며 1은 이동할 수 있는 칸, 0은 벽을 의미한다. 예제 1번을 보면서 문제를 이해해보겠다. 예제 1번의 최단 경로를 그려보면 위와 같다. 이러한 유형의 문제는 대부분 입력 값을 넣어줄 Map 배열과 방문 여부를 판단하는 visited 배열 두 가지가 필요하다. int[][] map = new int[N+1..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 처음엔 dfs를 이용해서 접근했지만 시간을 구하는 게 어려워져서 bfs로 접근했다. 문제에서 제시된 수빈이가 이동하는 방법은 총 3가지이다. 1. n+1 2. n-1 3. 2n 위 방법으로 1초마다 한 번씩 이동할 수 있다. 예제를 통해서 문제를 차근차근 이해해보겠다. 1. 초기 상태 (0초) 2. 1초 수빈이가 이동할 수 있는 곳은 n+1 → 6 n-1 → 4 2..