안녕

0. 문제 링크 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 1. 풀이 방법 방향의 우선순위는 무조건 오른쪽 위, 오른쪽, 오른쪽 아래로 해야 한다. 그리고 왼쪽 상단부터 왼쪽 하단으로 차례로 돌면서 길을 찾는다. 나는 따로 방문 표시 복구를 하지 않았는데, 어차피 위에서 가지 못한 길이라면, 아래에서도 가지 못하는 길이기 때문에 복구하지 않았다. 따라서 dfs로 문제를 풀었다. 2. 코드 import sys input = sys.stdin.readline..

0. 문제 링크 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 1. 풀이 방법 해당 문제의 핵심은 그룹 번호이다. DFS를 수행하던 도중 같은 그룹 번호를 만난다면 이는 싸이클이 생긴 것이고, Safe Zone을 하나 추가해야 한다. 하지만 만약 다른 그룹 번호를 만난다면, 그 그룹은 이미 Safe Zone이 있으므로, 그냥 break 하면 된다. 내 그룹이 해당 그룹에 편입한다고 생각하면 편할 것이다. (..

0. 문제 링크 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. 풀이 방법 이 문제는 DFS + DP이다. 안 그래도 어려운 두 개를 붙였으니 더 어려웠던 것 같다. https://minny27.tistory.com/42 [백준 1937] 욕심쟁이 판다 (Python) 문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤..

0. 문제 링크 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 1. 풀이 방법 해당 문제는 단순히 사이클이 존재하는 노드를 집합으로 넣으면 되는 문제이다. 나는 전혀 최적화를 하지 않고, 모든 노드를 살펴보면서 탐색하게 하였다. 물론 이 방법이 좋은 것은 아니지만, 그래도 꽤 시간은 빨랐다. 아무튼 DFS를 하다가 특정 노드가 이미 True로 설정되어 있다면, 이는 사이클이 생긴 것이므로 이를 ans set에 넣고 반환하게 하였다..

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.05.26 - [Computer Science/알고리즘] - [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘) [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘) 1. BackTracking 이란? Backtracking is used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criterion 즉, 되추적 기술은 특정 집합에서 주어진 기준에 대로 원소의 순 hi-guten-tag.tistory.com 1. Bran..