개발하는 고라니

5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net [DFS] 이런 DFS문제를 전에 풀어본 것 같다. 철수와 영희가 각각 i, j에 있을 때 철수가 왼쪽(-1), 오른쪽(+1)로만 움직일 수 있을 때 몇 번만에 영희를 만날 수 있는가? 와 같은 문제. 다만 처음에 오답을 받았다. 아무래도 DFS는 최단 거리를 찾기엔 부적합한 면이 없지않아 있으니 말이다. 다시 말해, 특정한 정점에 처음 도착했는데, 그 때가 최소값이 아닐 수 있다는 말이다. 그래서 대부분 BFS로 풀으신 것 같다. 하지만 DFS로도 264ms를 받고 AC했..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net [DFS] 0번부터 N-1번을 시작 정점으로 총 N번의 DFS를 실시하는데, 각 DFS가 끝나면 해당 정점의 visit[current] = false로 다시 변경한다. 이는 백트래킹 문제에서 주로 쓰던 방법이다. 해당 아이디어의 출처는 다음 링크에 있다. www.acmicpc.net/board/view/34026 그리고 DFS를 한층 한층 진행할 때마다 depth를 증가시키며, depth가 5가 되면 결과 flag를 true로 변경하고 루프의 진행을 멈춘다. # Code public class Main { static List[] list = new ArrayList[..

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