개발하는 고라니

2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net [BFS] 이전에 만났던 '백조의 호수', '탈출' 같은 문제처럼 2개의 BFS를 필요로 한다. 다만 이 문제는 치즈 내부에 공기가 차있을 경우 치즈 외부의 공기와 동일한 역할을 하지 못한다. 즉 치즈를 녹일 수 있는 조건에 영향을 미치지 못하기에 이것이 조금 까다로웠다. 그래서 airBFS라는 메서드를 실행할 때 마다, (0, 0)에서 공기를 퍼지게 하는 느낌으로 (0, 0)에서 BFS를 실행해 치즈를 만나면 숫자를 증가시켜 공기와 2번 이상 접촉한 ..

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net [DFS] 트리의 지름을 구하기 위해선, 1번 정점을 Root 정점으로 두고, 1번에서 DFS를 시작한다. 그 후 1번에서 가장 먼 정점 v1을 기록하고, v1에서 DFS를 해서 가중치의 합이 가장 큰 것을 반환하도록 한다. 처음에는, 입력을 받을 때 각 인접리스트의 사이즈가 가장 작은 것들을 배열이나 리스트에 담아서, 그 곳에 담긴 정점에서 DFS를 하며 가중치의 합이 가장 큰 곳을 찾아보았으나, 정점이 최대 10만개이기도 하고, 말단노드(간선이 1..

16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [BFS] 나는 보통 visit를 boolean으로 하여 true/false로 구분하지만, 이런 영역을 나눠야 하는 문제에서는 int visit[][]로 하는 편이 좋다. 점(i, j)에서 인접한 점과의 차(a)가 l = l && Math.abs(map[y][x] - map[ny][nx]) = l && Math.abs(map[y][x] - map[ny][nx])

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net [2개의 Queue를 이용한 BFS] 이와 비슷한 문제지만 좀더 어려운 문제가 '백조의 호수'라고 생각된다. 이 문제를 풀었다면 아래 문제도 풀어보길 추천하는 바다. [백준] 3197번 : 백조의 호수 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공 dev-gorany.tistory.com 고슴..

3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net # 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....X..

5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net [다익스트라 알고리즘 + DFS 또는 BFS] 이 문제를 풀기 위해선 다음과 같은 작업을 해야한다. 1. start -> end의 최단 경로 구하기 2. 최단 경로 제거하기 3. 다시 최단경로 구하기 1, 3번 같은 경우는 그냥 다익스트라를 이용하면 되나, 2번이 조금 까다로울 수 있다. 방법은 DFS나 BFS를 이용해 최단 경로를 제거하는 방법인데, 우선 최단 경로를 추가적인 인접 리스트 같은 곳에 저장해두도록 한다. //다익스트..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net [BFS or DFS] (BFS(위)에 비해 DFS(아래) 코드가 좀 더 간결하고 메모리와 시간 효율도 더 좋았다.) 문제의 난이도는 크게 어렵지 않았다. 2중 루프가 많이 사용되었다. 그래서 시간과 메모리에 민감한 문제였던 것 같다. 함수 내에서 빙산이 2부분으로 쪼개지는 시점의 time을 반환해야하고, 만약 빙산이 다 녹을 때 까지 2부분으로 나누어지지 않으면 0을 반환하는 문제이다. 처음 2차원 배열을 입력받는 map[][]과 map[i][j]의 주변..

2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net # 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N..