시작이 반

N과M 3번째 시리즈이다. 이번에는 방문했던 숫자를 다시 방문할 수 있다. visited를 써서 풀었지만 생각해보니 안써도 될 것 같다. visited를 모두 False로 하고 방문을해도 방문처리를 안한다. n, m = map(int, input().split()) visited = [False] * (n + 1) solve = [] def Dfs(depth): if depth == m: for i in range(m): print(solve[i], end=" ") print() # print(' '.join(map(str, solve))) # join을 사용하여 풀 수 도있다. join은 문자열을 합치는 함수이다. # solve에 있는 원소는 int형이기 때문에 map을 사용하여 string형으로 만들..

15649번에서 오름차순을 하고, 중복을 없앤 방식이다. 1. 재귀를 수행할때 반복문을 시작해야할 숫자를 같이 넣어준다. 현재 i 보다 +1 인 값을 건내줘서 반복문이 그 값부터 시작하게 한다. 2. list의 마지막 원소값을 확인하여 그 값보다 i 가 클경우만 재귀를 수행한다. 깊이가 0일땐 무조건 재귀 ** if depth == 0 or visit_number[len(visit_number) - 1] < i: n, m = map(int, input().split()) visit_number = [] def BackT(start, depth): if depth == m: for i in visit_number: print(i, end=' ') print() return for i in range(sta..

백트래킹의 기초 문제이다. 완전탐색을 하게된다. 재귀를 이용하여 풀게되는데 이때 더이상 탐색을 할 필요가 없다면 재귀 탐색을 멈추게된다. 첫 풀이 해당 숫자에 visited를 부여하여 방문을 했는지 계속 체크하고 visited를 deepcopy하여 넘겨주는 식으로 하였다. 이렇게 하면 숫자가 많아질수록 list를 엄청나게 많이 만들게 되고 또한 deepcopy를 하는데에 시간도 길리기 때문에 메모리, 시간 둘다 비효율적이다. ....... 정답 풀이 visited라는 상태 체크를 하는 것이 아니라, 방문한 숫자를 집어넣는 list를 만들어 풀게 된다. 1. 깊이가 출력하는 숫자의 길이가 같을경우 재귀를 멈춘다. 2. i : 1 ~ n 까지 반복을 하여 list에 i에 해당하는 숫자가 없을경우 i를 app..

미로와 같은 방식으로 풀 수 있지만 벽을 최대 한번 부실 수 있다는 조건이 있다. 처음 생각한 방법은 다음 좌표에 대해서 벽이 있을경우 그 벽을 깨고 그 자리에서 다시 BFS를 수행하는 것이었다. 즉 BFS( BFS ) 이렇게 중첩이 되는데 제출 결과 시간 초과 에러가 나왔다. 시간 복잡도를 보게되면 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색하니까 O(NM)^2)가 된다. 배열의 가로와 세로의 입력이 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000) 이렇게 제한이 되어있는데 N과 M이 1000일경우 NM은 1,000,000이 되고 NM^2은 1,000,000,000,000가 되니.. 시간초과가 뜨는게 당연하다. 3시간이나 붙잡고 풀었는데 참... 정..