의식이 흐르는대로 해보는 프로그래밍

목차 접근 스도쿠를 풀어내는 문제다. 스도쿠 문제는 N과M 문제와 더불어서 백트래킹으로 푸는 가장 대표적인 예제 중 하나이다. DFS를 수행하면서, 특정 조건을 만족하는지 체크하고 DFS가 끝나면, 다시 원래 상태로 되돌려놓는 알고리즘이다. 이렇게 DFS 알고리즘 시작단에 끝나는 조건을 명시해주면, 특정 조건이 맞는 케이스일 때까지 전체적으로 탐색을 진행할 것이다. 해결 백트래킹으로 해결하자. 0인 위치를 먼저 기록해두고, 0인 위치를 하나씩 채워나가는 방식으로 구현을 진행하자. 또한 스도쿠의 정답이 여러개가 나올 수 있음으로 종료단에, return이 아닌 exit를 이용해서 한번만 출력하고 프로그램을 종료시켜줘야한다. 안그럼 출력 초과가 뜬다.. 코드 sdoku = [] zero_idx = [] for..

접근 문제 자체는 복잡해보이지 않았다. 지나온 알파벳은 다시 들리지 않는다. 이게 이 문제의 중점이었던 것 같은데, 나는 백트래킹 최적화에 애를 먹어서 몇가지 기억하려고 남기려한다. 해결 사실 백트래킹 방법이 아니라, 충분히 BFS로 풀 수 있어보이지만 그냥 앞서서 N과M 문제 풀다보니, 백트래킹으로 해결하려고 시간을 썼다. 근데... 자꾸만 시간 초과가 나서 몇가지 최적화를 진행했다. 일단 백트래킹에 대해서 잠깐 서술해보자면, 영어 그대로 Back Tracking이다. 백트래킹은 재귀적으로 접근하는 알고리즘이다. 모든 경우를 고려하며, 재귀적으로 탐색을 진행하다가 특정 조건에 맞지않는 경우를 제외하고, 다시 탐색을 진행하는 것이다. DFS를 재귀로 구현할 때를 생각하면 형태가 거의 비슷하여 알고리즘의 ..