22년 11월 3주차 회고록 (스터디자랑)

import sys import numpy as np def calculate_distance(arr, x, y): distance = 0 arr[x][y] = distance while(sum(sum(np.where(arr== -1, True, False)))>0): xs = np.where(arr==distance)[0] ys = np.where(arr==distance)[1] distance += 1 for i in range(len(xs)): x = (xs+2)[i] y = (ys+1)[i] if x>=0 and x<len(arr) and y>=0 and y<len(arr): if arr[x][y] == -1: arr[x][y] = distance for i in range(len(xs)): x = (xs+2)[i] y = (ys-1)[i] if x>=0 and x<len(arr) and y>=0 and y<len(arr): if arr[x][y] == -1: arr[x][y] = distance for i in range(len(xs)): x = (xs-2)[i] y = (ys+1)[i] if x>=0 and x<len(arr) and y>=0 and y<len(arr): if arr[x][y] == -1: arr[x][y] = distance for i in range(len(xs)): x = (xs-2)[i] y = (ys-1)[i] if x>=0 and x<len(arr) and y>=0 and y<len(arr): if arr[x][y] == -1: arr[x][y] = distance for i in range(len(xs)): x = (xs+1)[i] y = (ys+2)[i] if x>=0 and x<len(arr) and y>=0 and y<len(arr): if arr[x][y] == -1: arr[x][y] = distance for i in range(len(xs)): x = (xs+1)[i] y = (ys-2)[i] if x>=0 and x<len(arr) and y>=0 and y<len(arr): if arr[x][y] == -1: arr[x][y] = distance for i in range(len(xs)): x = (xs-1)[i] y = (ys+2)[i] if x>=0 and x<len(arr) and y>=0 and y<len(arr): if arr[x][y] == -1: arr[x][y] = distance for i in range(len(xs)): x = (xs-1)[i] y = (ys-2)[i] if x>=0 and x<len(arr) and y>=0 and y<len(arr): if arr[x][y] == -1: arr[x][y] = distance return arr # arr = np.array([[-1]*100 for i in range(100)]) # # print(calculate_distance(arr, 0, 0)[30][50]) testcase_num = int(input()) for i in range(testcase_num): size = int(sys.stdin.readline().replace("\n", "")) array = np.array([[-1]*size for i in range(size)]) first = sys.stdin.readline().replace("\n", "").split(" ") end = sys.stdin.readline().replace("\n", "").split(" ") print(calculate_distance(array, int(first[0]), int(first[1]))[int(end[0])][int(end[1])])

dx = [1,2,2,1,-1,-2,-2,-1] dy = [2,1,-1,-2,-2,-1,1,2] cnt = [] def solution(l,from_coord,to_coord,count): if(from_coord == to_coord): cnt.append(count-1) return x, y = from_coord for i in range(len(dx)): x_tmp = x + dx[i] y_tmp = y + dy[i] if(x_tmp < 0 or x_tmp >= l or y_tmp < 0 or y_tmp >= l): return solution(l,[x_tmp,y_tmp],to_coord,count+1)

dx = [1,2,2,1,-1,-2,-2,-1] dy = [2,1,-1,-2,-2,-1,1,2] def solution(l,passed,to_coord,count): global cnt if(passed[-1] == to_coord): cnt.append(count-1) return x, y = passed[-1] for i in range(len(dx)): x_tmp = x + dx[i] y_tmp = y + dy[i] if([x_tmp,y_tmp] in passed or x_tmp < 0 or x_tmp >= l or y_tmp < 0 or y_tmp >= l): return passed.append([x_tmp,y_tmp]) solution(l,passed,to_coord,count+1) passed.pop() # cases = int(input()) # for case in range(cases): global cnt cnt = [] l = int(input()) from_coord = list(map(int,input().split())) to_coord= list(map(int,input().split())) solution(l,[from_coord],to_coord,1) print(min(cnt))

아직 푸는 중

재귀 또는 반복문을 통해 최단거리를 찾아야 하는데, 시간초과가 안나는 범위에서 어떻게 이동시켜야 할지 어떻게 최단거리를 구할지 생각하는게 너무 힘들었습니다...

어떻게 풀어야하는지 정말 막막했던 것 같습니다. 그리고 백준에서 numpy를 쓸 수 없어 더 좋은 방법을 생각해봐야할 것 같아요 ㅠㅠ

dfs에 겨우 조금 익숙해졌다고 생각했는데 오랫만에 적용하려고 하니 어려웠고, 게다가 bfs라는 비슷하지만 또 다른 탐색 알고리즘을 만나서 어려웠습니다..

모르면 배우자...

잘 모르겠으면 무작정 시도해보는 것도 좋은 방법 인 것 같습니다!

복습을 열심히 하자 꾸준히

그래프라는 알고리즘이 낯설고 익숙치가 않았는데 배울 수 있는 좋은 시간이였습니다. 비록 문제해결은 못했지만, 최단시간을 구할 때 그래프를 활용해 문제를 해결 할 수 있다는 것을 알게되었습니다!

그래프 문제를 풀 때 너무 많은 경우의 수가 생겨서 어떻게 풀어야할 지 정말 막막했는데 행렬이라는 좋은 도구를 이용할 수 있다는 것에 신선함을 느꼈고 좋았습니다. 그래도 낯설고 어려워서 많이 연습해봐야하는 부분 인 것 같습니다.

처음에 너무 막막하더라도 뭐라도 적다 보면 조금씩 해결 방법이 보인다는 것을 느꼈습니다! 금방 포기하고 답안을 참고하려 하지 않고 가끔은 그냥 계속 고민해 보는 것도 좋은 경험인 것 같습니다.