거창한 시작

www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 알고리즘 종류 - BFS - 구현 사고 과정 - 매 초마다, 사건은 두 가지가 동시에 일어난다. 1. 불이 움직인다. 2. 상근이가 움직인다. - 불이 있고, 또는 불이 움직일 곳으로는 상근이가 갈 수 없다. 그리고 상근이가 있는 칸에 불이 오는 동시에 상근이가 움직인다. 이를 구현하기 위해서는 동시간 대에 불이 먼저 움직이면 된다. * 0초 * 1초 + 왼쪽은 불이 먼저 움직인 사건이다. 동시간 1초대에서 빨간색은 불이 ..

www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 알고리즘 종류 - BFS 사고 과정 - 경우는 2가지이다. 1. 검 없이 공주님에게 달려간다. (1, 1)에서 시작해서 (n, m)에 도착하는 BFS. 2. 검을 찾고 공주님에게 달려간다. (1, 1)에서 (sword_y, sword_x) 검이 있는 곳에 갔다가 (n, m)에 도착하는 BFS - 두 가지 경우에서 나온 시간 중에 최소 값이 제한된 시간 이하인지 확인해서 결과를 출력한다. 구현(C..

www.acmicpc.net/problem/2024 2024번: 선분 덮기 각 테스트 케이스는 M(1 ≤ M ≤ 50,000) 과 "Li Ri"(|Li|, |Ri| ≤ 50,000, i ≤ 100,000)쌍으로 구성이 된다. 각각은 다른 행으로 분리되어 있다. 입력은 "0 0"으로 끝난다. www.acmicpc.net 알고리즘 종류 - 자료구조 사고 과정 - 현재 시점을 기준으로 다음에 들어올 시작점이 현재 시점 이하이면서 최대 끝지점을 찾으면 된다. 아래 예시를 보자. - m=10이고 7개의 선분들이 있다. 그려보면 아래와 같다. 1. 현재 시점 0을 기준으로 0이하인 시작점을 가지는 선분들은 [0, 1]과 [0, 5]이다. 이중에서 가장 큰 끝지점을 갖는 것은 [0, 5]이다. 시작점을 0에서 5로 ..

www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 알고리즘 종류 - 구현 - 브루트포스 - BFS 사고 과정 0. 땅을 나타내는 구조체를 생성한다. 0-1. 땅의 상태(0,1,2), 배양액의 색, 뿌려진 시간, 꽃이 피었는지 유무 1. 배양액을 뿌릴 땅을 조합으로 구한다. 1-1. 초록색 배양액을 먼저 DFS로 백트랙킹해서 구한다. 1-2. 이후, 붉은색 배양액을 DFS로 백트랙킹해서 구한다. 2. B..

www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 알고리즘 종류 - 다익스트라 사고 과정 - 간선의 가중치가 다르고 최단 거리를 구하는 다익스트라 문제이다. 또한, 조건이 2개이다. 조건이 1개일 때는, 1차원 배열을 사용해서 문제를 해결했다. 이번에는 조건이 2개으므로 2차원 배열을 이용해보자. * dp[i][j] = value : 시작점 1에서 i까지 가는데 최소비용 j으로 가는 최소 시간 value - 일반적으로 풀게..

www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 알고리즘 종류 - 다익스트라 사고 과정 - 아래와 같은 경우로 최단 거리 경로가 나올 수 있다. 그러면 하늘색 화살표마다 다익스트라 알고리즘을 적용한다. 첫 번째 경우로 예를 들면, S->G, H->E (G-H는 도로가 1개이다.)에서 경로들의 합을 구하고, S->E와 비교해서 같으면 된다. - 그런데 문제는 G와 H 중에 S와 가까운 노드는 무엇인가이다. S시작 다익스트라를 해보면, 2->1 VS 2->..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 알고리즘 종류 - 트리 - DFS 사고 과정 - 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 찾기 위해서 간단한 것부터 생각해보자. 노드 간에 이동거리가 모두 1이라고 해보자. * 아래 예시를 보자. 임의의 노드에서 출발하자. 본인은 노드 4를 골랐다. 노드 4에서 출발하여 가장 깊은 곳은 어딜까? 1이다. 그러면 이제 1에서 출발해보자. * 노드 1에서 출발해서 가장 깊은 곳은 어딜까..

www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 예시로 과정을 그려보면 아래와 같다. - 과정을 보면 다음과 같다. 1. 모래성은 기존 주변 파도 개수와 비교 2. 모래성은 기존 주변 파도 개수 + 새로 생성된 파도 개수와 비교 3. 모래성은 기존 주변 파도 개수 + 새로 생성된 파도 개수 + 새로 생성된 파도 개수와 비교 4. 모래성은 기존 주변 파도 개수 + 새로 생성된 파도 개..

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 시작층에서 시작하여 위 또는 아래로 움직인다. 1. 위로 움직일 때, 최고 층을 넘게 되면 중단한다. 2. 아래로 움직일 때, 1층 아래로 내려가면 중단한다. 3. 같은 층을 오는 경우는 제외한다. 왜냐하면, 같은 곳에 오면 같은 과정을 똑같이 하기 때문에 순환이 이루어진다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ..

www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K 3 -> 9를 거친다. 이때 목표 최소 비용이 4이면 ..