22년 11월 4주차 회고록

import queue as q def solution(maps): distances = calculate_distance(maps, 0, 0) x_length = len(distances) y_length = len(distances[0]) # print(distances) if distances[x_length-1][y_length-1] == 1: return -1 else: return distances[x_length-1][y_length-1] def calculate_distance(arr, x, y): # np.where 부분을 큐로 대체함 queue = q.Queue() distance = 1 queue.put((x, y, distance)) # 좌표를 넣음 arr[x][y] = distance dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while queue.empty() == False: x, y, distance = queue.get() # print(distance) # distance가 같은 깊이임에도 달라지는 문제가 발생 -> distance를 가지고 돌기 for i in range(len(dx)): xs = x + dx[i] ys = y + dy[i] # 아닌 조건일 때 continue를 해주지 않으면 if 가 성립하지 않는 경우 끊어짐 if xs<0 or xs>=len(arr) or ys<0 or ys>=len(arr[0]) or arr[xs][ys]>1: # x>=0 and x<len(arr) and y>=0 and y<len(arr): continue if arr[xs][ys] == 0: continue if arr[xs][ys] == 1: arr[xs][ys] = distance+1 # 다음 부터는 정상적으로 queue.put((xs, ys, distance+1)) # continue를 해주지 않으면 중단 됨 return arr print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]])) print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]))

from collections import deque # 북 동 남 서(시계방향) dx = [-1,0,1,0] dy = [0,1,0,-1] def bfs(maps): n = len(maps) m = len(maps[0]) visited = [[0] * m for i in range(n)] queue = deque() queue.append([0,0]) while(queue): x,y = queue.popleft() for i in range(len(dx)): x_tmp = x + dx[i] y_tmp = y + dy[i] if(x_tmp < 0 or x_tmp >= n or y_tmp < 0 or y_tmp >= m): continue if(visited[x_tmp][y_tmp]!=0 or maps[x_tmp][y_tmp]==0): continue visited[x_tmp][y_tmp] = visited[x][y]+1 if x_tmp==n-1 and y_tmp==m-1: break queue.append([x_tmp,y_tmp]) if(visited[n-1][m-1]==0): return -1 else: return visited[n-1][m-1] + 1

1. 시작점에서 목표지점까지 이동할때 맵의 크기를 벗어나는 것을 잡기가 힘들었습니다. 2. 최단경로를 찾기위해서는 모든 경로를 찾고 최단경로가 무엇인지 확인해야하는데 아직 모든 경로를 어떻게 구해야할지 고민중입니다. 3. 이동한 횟수를 어떻게 저장해야할지 고민중입니다.

1. queue를 이용해서 방문했던 곳을 기록하는 과정을 도입하는 데에 시간이 걸렸다. 2. if 문으로 특정 조건일때만 distance를 업데이트 할 때 에러가 발생했는데 그 이유을 파악하고 특정 조건이 아닐 때 continue를 사용하는 것이 어려웠다. 3. 같은 깊이임에도 distance가 다르게 계산되는 문제를 해결하는 아이디어를 떠올리는데 시간이 오래 걸렸다. 4. 무엇보다 여러 번 에러가 발생할 때 맞는 방법으로 가고 있다는 확신이 없어서 더 어려웠던 것 같다.

bfs, dfs를 풀 때 while문을 넣어야 할 지, 재귀로 풀어야 할 지 늘 고민이 된다. 또, 재귀로 푼다면 어떤 값을 넘기고 어떤 값을 return해야 할 지도 어렵다. 의도한 대로 결과가 나오기까지 시간이 항상 좀 오래 걸리게 되는 것 같다.

방향을 이동할떄는 배열을 활용해서 간단하게 구현할 수 있다!

코드를 작성하기 전 어떤 과정을 통해 문제를 풀 수 있을지를 메모하고 시작하는 것이 나중에 트러블 슈팅을 할 때도 좋은 것 같다.

재귀를 구현하기 어려울 때는 while문으로 먼저 풀어보자.

익숙하지 않은 알고리즘이라도 계속 풀다보면 조금씩 익숙해지니 문제를 해결하지 못하더라도 꾸준히 알고리즘 문제를 풀어야 겠다.

어렵더라도 열심히 도전하고 고민하는 과정에 익숙해지는 연습을 해야겠다.

bfs, dfs는 아주 여러 번 반복해서 풀어봐야 할 것 같다. 그리고 유형별로 어떻게 접근할 지 좀 정리해보는 과정이 필요할 것 같다.