(python3) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백트래킹 전형적인 dfs 백트래킹으로 해결할 수 있습니다. 매번 4방향으로 재귀를 돌고, 들렀던 알파벳을 만나면 끝내는 방식으로 적용합니다. 시간초과 이미 들렀던 알파벳을 어떻게 확인할것인가? 부분에서 어떤 방식과 자료구조를 취하느냐에 따라 시간초과가 발생할 수 있습니다. 저는 3가지 방식을 적용해봤습니다. 1. deque : 들렀던 알파벳을 deque 에 append 하고, 백트래킹에서 빠져나올때 pop 하는 형식. in 으로 들렀..
(python3) 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net N-queen 의 추억 n퀸.. 유명한 알고리즘 문제죠 처음 이 문제를 마주쳤을 때 혼자서 풀어보겠다고 이틀을 머리 싸맸던 기억이 나네요..ㅋㅋㅋ 이후 다른 알고리즘 책을 읽으면서 명료한 풀이법을 알게 됐었습니다. n-queen 의 기본 아이디어는 "우상향으로 같은 대각선의 경우 x+y 가 동일하다는것, 우하향으로 같은 대각선의 경우 x-y 가 동일하다는것" 입니다. 우상향, 우하향 대각선을 의미하는 배열을 각각 놓고 그 대각선에 이미 기물이 있다면 ..
(python) 백트래킹 디테일 구현 모듈을 잘 쪼개고, 백트래킹 함수를 잘 작성해주면 되는 문제였습니다. 이전에 작성한 청소년 상어와 결이 비슷합니다. 백트래킹 관련된 부분은 이 글로 대신합니다. https://jamong-5.tistory.com/53 백준 #19236 - [G2] 청소년 상어 : 구현, back tracking (python3) 아이디어 까다로운 상어 시리즈의 청소년 버전입니다. 이 문제는 시뮬레이션의 조건이 많기 떄문에 코딩 과정에서 스텝이 꼬이지 않도록 기능을 잘 분리해서 접근해주는게 좋습니다. 저 jamong-5.tistory.com 모듈화 아이디어 이 문제의 모듈화 같은 경우, "상하좌우 각 방향의 전체 칸을 모두 탐색한다" 라는 수행이 가장 기본이 되고, 이걸 방향마다 조합..
