시작이 반

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시간이나 붙잡고 풀었는데 참... 정..

수빈이가 다음 장소로 갈 수 있는 경우의 수는 3가지 이다. 3가지 경우의 수를 방문하면서 동생의 위치와 같을 때 까지 탐색을 한다. 현재 인덱스에서 다음 방문할 3개의 경우의 수를 모두 방문하여 동생의 위치와 같은 경우를 찾아야 하기 때문에 BFS를 사용한다. visited = [] 1차원 배열을 사용하여 해결할 수 있다. 처음 수빈이가 있는 인덱스를 방문처리(1로 지정)한다. 현재 노드에서 다음 3가지 인덱스를 방문한다. 여기서 방문처리는 (다음 노드 = 현재 노드 + 1) 로 나타 낼 수 있다. 인덱스가 동생의 위치와 같아질 경우 끝나게 되는데 이때 동생의 인덱스 까지 최소 몇번만에 도달하였는지 동생이 위치한 인덱스의 원소(다음 노드 = 현재 노드 + 1)로 알 수있다. 처음에 수빈이가 있는 인덱스..

2차원 리스트에서 로봇 청소기가 청소하는 구역을 구하는 문제 구현, 시뮬레이션 문제인데 맵 이동 문제는 보통 DFS, BFS로 푸는데 어떻게 풀어야 할지 몰라서 일단 생각나는데로 풀었다. 내일 DFS로도 풀어본다. 리스트 탐색문제는 dx, dy로 보통 푸는것 같다. 풀이 시작 위치를 방문(청소)을 했다고 지정해준후 함수를 시작시킨다. 무한루프를 사용 - 현재 방향의 왼쪽의 좌표를 구한다 - 구한 좌표가 방문(청소)를 하지 않고 벽이 아닐경우 - 현재 좌표를 구한 좌표로 바꿔준다. 방향도 현재방향의 왼쪽으로 바꿔주고 (ex. 현재 방향이 북(0)이면 서(3)) 방문(청소)처리하고 카운트 증가. - 벽이거나, 방문(청소)한곳이면 - 방향만 바꿈, 턴 횟수 증가 - 턴 횟수가 4일때 후진, 후진할수 없을경우 ..

7576번 2차원 토마토 문제와 같은 문제이다. 3차원 배열은 [z][x][y]인 것을 기억하자 또한 3차원 배열에서 Max값을 얻기 위해 쉽게 얻는 방법이 있는지 확인할려고 검색을 해본결과 2차원 배열에서 max(map(max, graph)) 이런식으로 하면 나온다고 하여 응용을 해서 max(map(max, max(graph)))를 사용하였는데 틀렸다고 나왔다. map사용법을 아직 잘모름... 3중포문을 사용하여 Max값을 구함 from collections import deque import sys input = sys.stdin.readline col, row, h = map(int, input().split()) graph = [[list(map(int, input().split())) for _..

미로 문제와 동일한 문제이다. 하지만 익은 토마토가 여러개 있을경우 그 토마토에 대해서 bfs처리를 동시에 해줘야한다. 처음에는 만약에 익은토마토가 여러개이고 안익은 토마토로 연결되어있으면 익은토마토의 개수만큼 나눠주면 되지아 않을까하고 풀어봤는데 아니었다. 어떻게 동시에 bfs를 돌려야 하는지 고민하는데 쓰레드 밖에 도저히 생각이 나지 않아서 알아본결과 큐에 익은 토마토를 넣어주면 되는 것이었다. 간단한 방법이었지만 생각이 나지 않으면 풀 수 없는 문제.. bfs에서 큐를 왜사용하는지 알아야함 from collections import deque import sys input = sys.stdin.readline col, row = map(int, input().split()) graph = [list..

미로 문제 즉, 최단거리 문제는 BFS를 사용하여 해결할 수 있다. 현재 위치에서 가장 가까운 점을 먼저 방문하기 때문이다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 시작 좌표(0,0)를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 좌표를 꺼내 해당 좌표의 인접 좌표(상, 하, 좌, 우)중 방문하지 않고, 해당 좌표의 값이 0이 아닌 경우 좌표를 모두 큐에 삽입하고 방문처리를 한다. 해당 좌표의 값을 이전 좌표의 값 +1 로 증가 시킨다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 답 : n, m의 좌표에 있는 값 (해당 풀이에선 0부터 시작함으로 n-1, m-1이다.) import sys from collections import deque input = sys.s..