시작이 반

백트래킹으로 구현할 수 있는 문제이다. 우선 index 0 ~ 80 의 칸을 검사한다. 해당 칸이 빈칸일경우 해당 칸에 들어갈 수 있는 숫자를 구한다. def AbleNumber(n, m): ableNumber = [1, 2, 3, 4, 5, 6, 7, 8, 9] for i in range(9): if graph[n][i] in ableNumber: ableNumber.remove(graph[n][i]) for i in range(9): if graph[i][m] in ableNumber: ableNumber.remove(graph[i][m]) sub_n = n // 3 sub_m = m // 3 for i in range(sub_n * 3, sub_n * 3 + 3): for j in range(sub..

NxN크기의 체스판이 주어졌을때 퀸을 서로 공격할 수 없게 N개 놓을 수 있다. N개를 놓을 수 있는 경우의 수를 구하는 문제인다. N개를 놓을 수 있다는 것은 한 행에 한개씩 놓을 수 있으면 된다는 소리이다. 퀸은 대각선, 열, 행 이렇게 움직일 수 있다. 즉, 어떤 위치에 퀸이 놓여지면 해당 대각선, 행, 열은 더이상 다른 퀸을 놓을 수 없게 된다. 해당 행에서 열을 순회하면서 놓을수 없는지 판단하며 상태 트리를 만들게 된다. ex) 퀸이 0,0에 있다면 0,0에 퀸을 놓았다면 1,2에 놓을 수 있다. 1,2에 퀸을 놓았는데 행이 2인 곳에 퀸을 놓을 수 있는 자리가 없기 때문에 이전 상태로 올라간다. 1,3에 퀸을 놓으면 2,1에 퀸을 놓을 수 있다. 2,1에 퀸을 놓았는데 행이 3인 곳에 퀸을 놓..

흠...ㄷㄷ 아이디어는 생각했는데 구현이 잘안된다.. 처음 생각한 아이디어는 각 숫자에 대해서 사용했는지 체크하고 재귀를 돌리는 것이었는데 잘 안되서 다른 방법을 사용하였다. 다음으로 생각한 아이디어는 list를 하나 만들어 방문한 숫자들을 append하는데 깊이가 증가할수록 구분할 수 있게 -1을 넣어줬다. 반복문을 돌면서 list의 마지막 원소와 append하려는 원소가 같으면 append를 하지 않고 재귀도 돌리지 않는다. for문이 끝나면 해당 깊이에서 append한 원소들을 제거한다. 사실 처음 생각한 아이디어가 더 쉬운 방법인데 시간만 날렸... 다른사람의 정답을 본 결과 for문을 돌리기 전에 used라는 리스트를 만들어주고 방문하지않고 사용되지 않았을때 used에 해당 숫자에 대해 표시(T..

입력으로 n개의 숫자를 임의로 받는다. 이를 list형태로 저장하고 숫자가 작은 것부터 탐색을 해야 하기 때문에 오름차순으로 정렬을 한다. 이전 방문 노드보다 같거나, 큰 숫자를 append한다. ( if depth == 0 or solve[depth - 1]

입력으로 n개의 숫자를 임의로 받는다. 이를 list형태로 저장하고 숫자가 작은 것부터 탐색을 해야 하기 때문에 오름차순으로 정렬을 한다. 이전 노드들도 다시 탐색할 수 있다. (반복문에 조건문이 없어도됨) 반복문을 사용하여 모든 노드들을 탐색한다. 오름차순으로 정렬한 리스트의 i번째 값을 append, pop 한다. n, m = map(int, input().split()) my_list = list(map(int, input().split())) my_list.sort() solve = [] def Dfs(depth): if depth == m: print(' '.join(map(str, solve))) return for i in range(n): solve.append(my_list[i]) Dfs..

N과 M 5의 확장 문제 이다. 입력으로 n개의 숫자를 임의로 받는다. 이를 list형태로 저장하고 숫자가 작은 것부터 탐색을 해야 하기 때문에 오름차순으로 정렬을 한다. 이전 방문 노드보다 큰 숫자를 append한다. 반복문의 i를 solve 리스트에 append, pop 하는 것이 아닌 오름차순으로 정렬한 리스트의 i번째 값을 append, pop 한다. 사실 visited를 써서 풀었는데 visited는 없어도 된다. if depth == 0 or solve[depth - 1] < my_list[i] 여기서 이전 노드보다 작은 노드들은 걸러지기 떄문이다. visited를 써야하는 경우는 이전노드들만 방문처리 되고 다른 노드들은 탐색할 경우이다. n, m = map(int, input().split(..

N과 M 5번 문제는 1부터 n까지 숫자가 있는 것이 아니라 입력으로 n개의 숫자를 임의로 받는다. 이를 list형태로 저장하고 숫자가 작은 것부터 탐색을 해야 하기 때문에 오름차순으로 정렬을 한다. 이후는 기존 n과 m의 풀이 방법과 같다. 대신 반복문의 i를 solve 리스트에 append, pop 하는 것이 아닌 오름차순으로 정렬한 리스트의 i번째 값을 append, pop 한다. n, m = map(int, input().split()) my_list = list(map(int, input().split())) my_list.sort() solve = [] visited = [False] * n def Dfs(depth): if depth == m: print(' '.join(map(str, so..

N과 M 3에서 중복을 제거한 문제이다. 반복문에 if depth == 0 or solve[depth - 1]