공부 기록

✏️ 문제 문제 파악입력값은 점을 기준으로 주니까 배열로 구현하려 할 때 조금 헷갈렸다. 그래서 아래와 같이 그림 그리니 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값은 그대로, 오른쪽 위 꼭짓점의 x, y좌표값은 -1씩하면 됐었다. 직사각형이 있는 영역은 방문하면 안되는 영역이므로 -1로 표시했다. 아 그리고 이 문제는 DFS로 풀었을 때 재귀를 사용하면 RecursionError가 발생하므로 나는 재귀 대신 스택을 사용해서 풀었다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드import sysinput = sys.stdin.readlinem, n, k = map(int, input().split())graph = [[0] * n for __ in range(m)]visited = ..

✏️ 문제 문제 파악최소 이동 거리를 구하므로 BFS를 사용해야 한다.또한 나이트는 8가지 방법으로 움직일 수 있으므로 다음과 같이 방향 배열을 구성했다.d = [(-2, -1), (2, -1), (-2, 1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)] x, y 좌표를 deque에 넣을 땐 "q = deque([(x, y)])" 라는 걸 알고 있자! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinefor _ in range(int(input())): l = int(input()) visited = [[0] * l for __ in range(l)..

✏️ 문제 문제 파악연산의 최솟값을 구해야 하므로 BFS를 사용해서 풀어야한다.이 문제에서 배열로 풀게 되면 A와 B의 범위가 매우 커서 배열 초기화시 메모리 초과가 뜨게 된다.그래서 배열 대신 딕셔너리 { } 를 사용하면 필요한 노드에 대해서만 메모리를 할당하여 메모리 사용량을 줄일 수 있다! 알고리즘그래프 이론그래프 탐색너비 우선 탐색그리디 알고리즘  코드from collections import dequea, b = map(int, input().split())graph = {}def bfs(v): q = deque([v]) graph[v] = 0 while q: node = q.popleft() if node == b: retur..

✏️ 문제 문제 파악같은 알고리즘의 문제 중 11725번 트리의 부모 출력 문제가 생각난 .. 매우 비슷함인접리스트를 활용하면 쉽게 풀 수 있다! 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())a, b = map(int, input().split())graph = [[] for _ in range(n+1)]visited = [0] * (n+1) for _ in range(int(input())): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x)def bfs(v)..

✏️ 문제 문제 파악BFS 사용하는 문제 중 11725번 트리의 부모 찾기가 생각났던 문제..인접리스트를 사용하면 쉽게 풀 수 있다! 알고리즘그래프 이론그래프 탐색너비 우선 탐색최단 경로플로이드-워셜  코드from collections import dequen, m = map(int, input().split())graph = [[] for _ in range(n+1)]cnt = []for _ in range(m): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x)def bfs(v): q = deque([v]) visited[v] = 1 while q: node = q.popleft() for neigh..