728x90 백트래킹12 [python] 백준 2580 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 해결 스도쿠는 문제 해결 방식을 이해하면 풀기 쉽다. 먼저 값이 0인(빈칸) 좌표를 찾는다. 1부터 9까지 값을 대입해가며 대입했을 때 그 행, 그 열, 박스 안 숫자에 중복이 없는지 확인을 하고 문제 없으면 다음 빈칸을 채우는 코드를 짜면 된다. 빈칸이 없어질 때 까지 문제가 생기지 않으면 그 스도쿠 판을 출력하면 된다. CODE def find_empty(): for i in range(.. 2023. 4. 10. [python] 백준 2239 스도쿠 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 해결 처음에 보면 까마득하다.(스도쿠 옛날에 풀어본 것 같은데 까먹기도 하고 실제로 싫어해서 싫어하는 문제..) 하나씩 확인해가며 풀어야겠다는 것은 알겠는데 구현을 잘 못하였다. (시간초과) 다른 분의 풀이를 보면서 깔끔하게 푸는 방법을 배울 수 있었다. 값이 0인 좌표 (i,j)를 찾아서 1부터 9까지 넣을 수 있는 값을 대입해보고 다음 0값을 가진 좌표 (p,q)를 또 가져와 계속 .. 2023. 4. 10. [python] 백준 18428 감시 피하기 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 문제 해결 벽 3개를 세우는 경우의 수를 모두 해보는 수밖에 없다. 3개를 세우고 'T'(teacher)을 중심으로 동, 서, 남, 북 모든 좌표를 보면서 T와 'S'의 사이에 이미 O가 있으면 넘어가는 방면 없으면 바로 다음 경우의 수를 확인하면 된다. 만약 모든 T와 S 사이에 O로 블로킹(blocking)이 된다면 가능한 사건이므로 YES를 출력하고 코드를 끄면(exit) 된다. C.. 2023. 4. 4. [python] 백준 2661 좋은수열 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 문제해결 문자열을 잘라서 앞에 문자열과 겹치는 것이 있는지 확인하는 문제 겹치는 것이 있으면 바로 그만두고 다른 경우의 수 찾기 for문이 많아 시간복잡도 걱정이 있었다. (사실 그래서 다른 분들의 코드를 많이 참고하였다.) 백트래킹의 전형적인 문제 CODE import sys input= sys.stdin.readline n = int(input()) result = [] def check(result, c.. 2023. 3. 27. 이전 1 2 3 다음 728x90