개발하는 고라니

9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net [Dijkstra * 3] 발상의 전환이 필요한 문제라고 생각된다. 문제에서 죄수 2명이 등장하여 이 2명이 여는 문의 개수를 세려고 하니, 잡아야 할 문제점이 잡히지 않았다. 그래서 여러 사람들이 사용한 제 3의 인물을 등장시켜 3명이 문을 여는 것으로 문제를 풀었다. 죄수 2명은 감옥 안에 주어지고, 제 3의 인물 상근이는 (0, 0)에서 시작한다. 이 3명은 모두 다익스트라 (BFS로 해도 무관하다고 생각됨)를 이용해 모든 문을 열고, 각 지점마다 몇 개의 문을 열고 ..

1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net [Kruskal Algorithm] n개의 우주신과 황선자씨의 좌표를 받고, 각 n개의 정점에 대해 이중루프를 돌며 간선을 만들어준다. 이 때 하나의 정점 v는 n-1개의 간선을 갖는다. 만들어진 모든 간선 정보를 List에 담는다. m개의 정점간 연결 정보를 받으며 주어진 정점들은 연결되었다고 parent 배열에 표기한다. List를 정렬하고, 크루스칼 알고리즘을 통해 모든 정점을 연결한다. # Code public class Mai..

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])

B로 놓느냐, A

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

1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net # 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다. 문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, ..