문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 설명 동전이 있는 곳에 쓰여 있는 숫자 X를 본다. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다. 처음 위치인 (0, 0)에서 시작하여 DFS을 진행한다. 나중에 사이클이 만들어지는지 확인하기 위한 visited 배열과 같은 좌표를 또 방문할 때 가지치기하기 위한 dp 배열을 만든다. DFS를 진행하..
문제 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 설명 1 ≤ i < j ≤ M인 i와 j를 고른 뒤, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 1,000,000보다 작거나 같은 자연수인 N을 위의 연산을 K번 하는데 이는 바뀐 수도 1,000,000보다 작거나 같은 수라는 뜻이므로 1,000,000 크기의 visited 배열을 만들어 현재 depth에서 이미 만들어진 수는 또다시 연산을 수행하지 않도록 한다 그리고, queue를 만들어 처음에 N을 넣고 BF..
문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 설명 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. 물도 매 분마다 비어있는 칸으로 확장하는데 물이 있는 칸과 인접해있는 비어있는 칸은 물이 차게 된다. 고슴도치는 물로 차있는 칸으로 이동할 수 없고 물은 비버의 소굴로 이동할 수 없다. 둘 다 돌을 통과할 수 없다. 비어있는 곳, 물이 차있는 지역, 돌, 비버의 굴, 고슴도치의 위치를 저장할 map[][]을 만들어 저장..
문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 설명 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다. 암호를 이루는 알파벳은 암호에서 증가하는 순서로 배열되어 있다. 먼저, 입력받은 알파벳을 알파벳 순서대로 정렬한다. 자릿수는 L이고 알파벳 수는 C이므로 암호의 첫 알파벳은 input[0] ~ input[C-L] 이 될 수 있다. 암호의 길이를 나타내는 length, 모음의 개수를..
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 설명 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 따라서, 'a', 'c', 'i', 'n', 't'는 반드시 배워야 하는 글자이다. 현재 배운 글자 수를 selectedCount 라 하고 초기값으로 5로 설정한다. 알파벳 개수만큼 원소로 하는 visited 배열을 만들어 'a', 'c', 'i', 'n', 't'에 해당하는 값은 true로 설정한다. sel..
DFS DFS(Depth-First Search)는 깊이 우선 탐색이라고 부른다. 한 경로로 최대한 깊숙하게 들어가서 탐색한 후 다시 돌아가 다른 경로를 탐색하는 방식 일반적으로 재귀함수를 이용하여 구현하며 Stack을 이용하여 구현하기도 함 구조상 Stack Overflow에 유의해야 함 DFS 활용 : 백트랙킹, 단절선 찾기, 위상정렬, 사이클 찾기 등 DFS 구현 1. 체크인 2. 목적지인가? 3. 연결된 곳을 순회 4. 갈 수 있는가? 5. 간다 6. 체크아웃 static int[][] graph; static boolean[] visited; static void dfs(int index) { // 1. 체크인 visited[index] = true; // 2. 목적지인가? if (종료조건) {..
