거창한 시작

www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 조건을 다음과 같다. * 오작교 조건 1. 1분 동안 유지 2. 주기대로 생성 3. 교차 절벽에 생성 금지 4. 이미 생성된 절벽에 오작교 겹쳐서 생성 금지 * 다리 건너는 조건 1. 오작교가 M주기로 생성될 때, 견우는 오작교 주변에서 M-1시간이어야 한다. (본인은 이 조건이 이해가 안되서 고생했다. 마치, 건너기 전에 다리가 생성되었는지 모르고 있다가 건..

www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 알고리즘 종류 사고 과정 1. 욱제를 9방향으로 움직인다. 2. 벽을 내린다. - 고려해야할 상황은, 욱제가 벽을 피하기 위해서 이전 시간대에 갔던 위치를 다시 갈 수 있다. 따라서 방문을 체크하는 배열을 시간대에 따라 초기화해야 한다. 구현(C++) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464..

www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 사이클을 형성하기 위하기 위한 조건 * 시작점으로 돌아온다. * 최소 변의 개수가 4개이다. - 주변을 탐색하는 것이 아닌 깊이 우선 탐색하기 때문에 DFS를 사용한다. - 방문했던 곳을 확인하는 배열(isVisited)로 재방문을 하지 못하면 시작점에 도달할 수 없다. 그렇다고, 재방문을 허락하면, 무한히 순환한다. 그러면 시작점을 어떻게 방문할 수 있..

www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 알고리즘 종류 - BFS - 구현 사고 과정 - 구해야 하는 항목은 3가지이다. * 방의 개수, 가장 넓은 방의 크기, 하나의 벽을 허물었을 때 가장 큰 방의 크기 - 문제에서 제시해 주고 있듯이 비트 연산을 사용하면 쉽게 풀 수 있다. * 간단하게 하는 방법을 알아보자. + 1은 0001, 2는 0010, 4는 0100, 8은 1000 이다. + 12는 1100이다. 위에서 1000과 0100의 합으로 ..

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