Backtracking

[백준] 1948. 임계경로 - Python

[Platinum V] https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 풀이 1 (오답) 문제를 보자마자, 그냥 크게 생각하지 않고 DFS(혹은 BFS..?) 느낌? 그냥 그래프 탐색으로 풀어본 결과. MLE가 나오긴 했지만, 다시 보니 지난 거리 개수를 셀 때 중복을 허용했기 때문에 틀린 코드다. MLE. (메모리 초과) / WA. from collections import deque n = int(input()) ..

[백준] 1987. 알파벳 - python

[Gold IV] https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 1 이건 그냥.. DFS, Backtracking 이용해서 Recursion으로 풀면 되겠다- 라고 간단하게 생각했다. 그런데 가볍게 짠 코드에서 TLE. import sys sys.setrecursionlimit(100000) R, C = map(int, input().split()) board = [list(input()) for _ in range(R)] res..

[백준] 2239. 스도쿠 - 파이썬

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 1, 풀이 2 모두 PyPy3 기준 AC 가능(통과 가능) 풀이 1 Backtracking을 이용해 풀 수 있는 문제. 스도쿠를 이차원 배열에 저장하고, 0이 있는 좌표들을 리스트에 저장. 백트래킹을 이용해 모든 0이 있는 칸에 가능한 숫자를 채워준다. recursion의 depth는 9x9 스도쿠이기 때문에 최대 81. recursion error를 걱정할 만한 깊이가 아니니 안심하고..