문제 이해 단계 https://www.acmicpc.net/problem/1967 문제가 굉장히 복잡하게 쓰여있는데 사실 간단하다. 노드에서 노드로 가는 데에는 각각의 가중치가 존재한다. 이때, 한 트리의 리프(가장 아래에 있는 노드)에서 다른 리프로 가는 경로가 존재할 것이고, 당연히 각각의 가중치가 존재한다. 이때, 한 리프에서 다른 리프로 가는 경로에서 얻을 수 있는 가중치 합 중 가장 큰 가중치 합을 구하는 문제이다. 예시로 된 그림을 보면 더 이해가 간단히 될 것이다. 문제 접근 단계 리프 노드를 알아내기 위해서는 연결된 노드를 계속해서 타고 들어갔을 때, 마지막 노드는 연결된 노드가 없다. 즉, 해당 노드에서 여러 노드가 연결되어 있다면, 갈림길의 경우의 수를 타고 들어가는 합을 모두 구한 후..

문제 이해 단계 사람이 0부터 N-1까지 넘버링되어 있고, 친구 관계가 A - B - C - D - E 이런 식으로 "하나의 키가 다른 하나의 값이 되는 구조가 4개가 되는 구조가 있느냐" 를 따지는 문제이다. 이를 예시 2번에 나와있는 그림으로 그려보자면 이런 식이다. 여기서 가능한 구조는 (0-3-2-1-4), (4-1-0-3-2), (2-3-0-1-4) 등으로 재방문을 제외하고 방문하는 곳이 4곳 이상이면 된다. 이렇게 생각해 보면 문제 이해는 간단하게 끝난다. 문제 접근 단계 연결된 노드의 개수를 깊이라는 측면으로 가정한다. 또한 어떤 노드의 값이 다른 노드의 키가 되는 것을 보면 DFS로 푸는 것이 더 적절하다고 생각했다. 이 문제에서의 핵심은 어떤 노드에서 시작한 DFS 중, 단 하나라도 연결..

문제 이해 단계 https://www.acmicpc.net/problem/17836 맵 크기 N M이 주어지고, 주어진 시간 T 안에 벽을 피해 오른쪽 아래에 도달해야 한다. 최단 거리를 구하는 문제인데 특이한 점은 그람이라는 검이 있는 곳에 도달하면 벽을 뚫고 지나갈 수 있다는 점이다. 즉, 그람을 획득한 순간 어디든 자유롭게 다닐 수 있다는 뜻이다. 이 조건이 있을 때, 왼쪽 위에서 오른쪽 아래까지 도달하는데 걸리는 최단 시간을 구하는 문제이다. 문제 접근 단계 최단 거리를 탐색하는 대표적인 2차원 BFS문제이다. 조금 특이한 점은 그람이라는 검의 존재이다. 그람을 획득하는 순간 벽의 유무는 상관 없어진다. 즉, 그람을 획득하는 순간부터는 벽이 없다고 가정하고 BFS를 진행해도 된다는 뜻이다. 위 문..

문제 이해 단계https://www.acmicpc.net/problem/1600원숭이가 두 가지 방법으로 이동하는데 위의 그림처럼 움직이는 것이 일정 횟수만큼 가능하다.1. 상하좌우 한 칸씩 이동2. 위 그림처럼 이동 -> 횟수 제한이 상황일 때 좌측 상단에서 우측 하단까지 가는,  최소 움직임(최단 거리)을 구하는 문제 문제 접근 단계일단 2차원 배열이 주어지고 상하좌우로 움직일 수 있으니 BFS문제라고 생각했다.거기에다가 특수한 움직임(말의 움직임)이 섞였으니 BFS에 새로운 경로를 추가해서 푸는 문제라고 생각했다.한 칸씩 이동할 때는, 한 번 방문한 위치를 다시 방문하지 않는다.왜냐하면 방문한 곳을 다시 방문하는 순간, 그 경로는 최단 경로라고 할 수 없기 때문이다.또한 동일한 위치의 방문 횟수는 ..

문제 이해 단계 https://www.acmicpc.net/problem/14502 3개의 벽을 배치하여 얻을 수 바이러스가 퍼지지 않는 방의 최대 개수를 구하는 문제이다. 바이러스는 십자가 모양으로 퍼지고 벽을 통과할 수 없다. 입력으로 연구소의 지도가 주어지고, 출력으로 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하는 문제이다. 이해 자체는 오래 걸리지 않았던 문제이다. 문제 접근 단계 이 문제의 포인트는 무조건 3개의 벽을 활용해야 한다는 점과 입력으로 주어지는 N과 M의 크기가 최대 8로 엄청나게 작다. 게다가 시간제한이 2초, 메모리 제한이 512MB로 넉넉하기 때문에 벽 3개를 전부 다 탐색하는 브루트포스 방식을 사용해도 된다고 생각했다. 그리고 바이러스는 십자가 모양으로 한 칸씩 퍼지는..

문제 이해 단계 https://www.acmicpc.net/problem/18513 문제 이해 자체는 그렇게 어렵지 않은 문제. N개의 샘터와 K개의 집이 주어진다. 이후 샘터의 위치가 지정되고 집의 위치를 지정하는데 집이 샘터에 멀어질수록 불행도가 올라간다. 이때, 불행도의 합을 최소화할 수 있도록 집을 배치한 후, 그때의 합의 최솟값을 구하는 문제이다. 샘터에는 집을 지을 수 없고, 집을 겹쳐지을 수도 없다. 문제 접근 단계 불행도를 최소화하기 위해서는 샘터에 양옆에 차곡차곡 최대한 붙여서 짓는 것이 가장 좋다/ N개의 샘터가 있다면, N개의 샘터를 하나씩 돌아가면서 양쪽에 집을 두면서 진행하는 것이 좋다. 이런 동작원리가 BFS와 흡사하다고 생각하여 BFS로 접근하기로 했다. 1. 모든 샘터들을 큐..

문제 이해 단계 짧아서 이해하기 간단한 문제 N개의 점과 M개의 선이 입력된 후, 그 아래에 연결 노드의 정보들이 입력된다. 그때의 연결 노드의 개수를 구하는 문제이다. 문제 접근 단계 BFS나 DFS로 푸는 대표적인 연습용 문제라서 유추할 필요도 없다. 방향이 없는 그래프이기 때문에 양쪽 모두 연결된다는 점만 기억하면 된다. 예를 들어, 2 5가 입력으로 주어진다면 2 -> 5와 5 -> 2가 동시에 연결되는 것과 동일한 것이다. 나는 이 문제를 벡터와 큐를 이용하여 BFS로 풀었다. 문제 구현 단계 void bfs(int start) { queue q; q.push(start); c[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); fo..

문제 이해 단계 문제 자체는 짧고 이해도 간단한 문제. X축 하나만 존재하고 점 N에서 점 K까지 가는데 총 3가지 방법이 존재한다. 1. 2 * N칸 이동 -> 시간소모 = 0초 2. +1칸 이동 -> 시간소모 = 1초 3. -1칸 이동 -> 시간 소모 = 1초 이 세 가지 방법을 이용하여, 점 N에서 점 K까지 가는 최소 시간을 찾는 문제이다. 문제 접근 단계 처음에는 최소시간을 찾는 것이기 때문에 그리디 문제인 줄 알았다. 하지만 그리디 문제의 조건은 매 순간마다의 최적의 답이 문제의 답이 되어야 한다. 이 문제에서는 나중에 분석한 답이 더 최소 시간 일수도 있기 때문에 그리디로 풀기엔 적합하지 않다. 그래서 x축에서 한 점을 기준으로 양쪽을 탐색하여 K를 찾는 BFS 방식을 사용하기로 했다. 다른..