개발하는 고라니

2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net [BFS] 개인적으로 브루트 포스 방법을 좋아하지 않는다. 문제에서 정점은 최대 50x50 = 2500개라서 브루트 포스를 해도 시간이나 메모리적으로 촉박하진 않지만, 다른 방법으로 풀어보고 싶었다. 그래서 주어진 map에서 'L'이면 주변의 'L'이 몇 개인지 세어 우선순위 큐에 좌표(i, j)를 넣었고, 주변에 'L'이 가장 적은 좌표부터 꺼내어 BFS를 하며 거리를 측정하였다. 그러나 이 방법에는 치명적인 오류가 있었다. W L W L W L L L L L L..

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[..

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..

B로 놓느냐, A

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net # 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s..

1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net # 문제 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-..