공부 기록

✏️ 문제 문제 파악최소 치환 횟수를 구하므로 BFS를 사용해서 풀어야 한다.인접리스트를 활용해서 풀어야 하는 문제라 다음과 같이 입력을 처리하였다.for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) 그 후엔 graph를 돌며 visited 배열에 치환 횟수를 저장하며 풀었다. 예제들은 잘 출력되는데 자꾸 틀렸다고 나오길래 찾아보니 a와 b가 같은 문자라면 치환 횟수가 0이므로 0을 출력해야 한다는 것을 빼먹고 있었다.. 예제는 잘 풀리는데 퍼센트 높을 때 틀리는 사람은 a와 b가 같은 문자였을 때를 처리했는 지 확인해 보는 것을 추천! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드..

✏️ 문제 문제 파악16173번 점프왕 쩰리 (Small) 와 비슷한 문제이다. 하지만 메모리가 매우 작습니다...... (메모리 초과 3번이나 떴다ㅠ) 메모리 초과를 해결한 방법은 다음과 같다.visited 배열을 없애고 graph 배열로만 방문했는 지 구분했다.이미 방문했던 위치는 또 돌 필요가 없으므로 바로 continue를 통해 메모리를 절약하도록 했다.if graph[x][y] == 0: # 이미 방문했던 위치 continue덱에 값을 새로 넣은 후에 방문 표시를 하는 보통의 경우와 달리 덱의 값을 꺼내는 즉시 바로 방문 표시를 하였다.x, y = q.popleft()graph[x][y] = 0 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections im..

✏️ 문제 문제 파악graph 2차원 배열에 1을 양, 2를 늑대로 표시했다.1 → 양2 → 늑대그리고 visited 2차원 배열의 값을 세 가지로 나눠서 대입하고 이를 이용해 조건문을 구분하였다.0 → 방문 안한 필드1 → 방문한 필드-1 → 울타리 부분으로 방문하면 안되는 필드또한 이 문제의 경우 가로, 세로로 연결되어 있는 필드는 같은 영역이므로 방향 배열을 다음과 같이 구성했다.d = [(1, 0), (0, 1), (-1, 0), (0, -1)] BFS를 돈 후에 배열을 return 했는데 인덱스 0에는 양의 수, 인덱스 1에는 늑대의 수로 하였다.그리고 return 된 값에서 if 문을 돌아양의 수가 많으면 늑대를 우리에서 쫓아내므로 늑대의 수가 0이라 인덱스 1을 0으로 바꾸고 출력할 nu..

✏️ 문제 문제 파악최댓값을 출력하므로 BFS를 활용하여 풀었다. 아기 상어의 위치에서 공간 내 거리가 각각 얼마나 걸리는 지 safety 배열에 담았다.그리고 A 아기 상어에서 멀어도 B 아기 상어에서의 거리가 더 가까우면 그 거리를 대입해야 하므로 min을 사용하여 safety 배열에 담았다.  safety 이차원 배열에서 max 값을 구해야 하므로 max(safety) 쓰면 값이 안나온다! 주의하자! 알고리즘그래프 이론그래프 탐색너비 우선 탐색브루트포스 알고리즘  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [[0] * (m) for _ in range(..

✏️ 문제 문제 파악7562번 나이트의 이동 의 업그레이드 버전인 듯? 똑같이 풀면 쉽게 답이 나온다! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())graph = [[0] * (n) for _ in range(n)]visited = [[0] * (n) for _ in range(n)] d = [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)]start_x, start_y, end_x, end_y = map(int, input().split())def bfs(x, y): q = deque([(x, y)]) vi..

✏️ 문제 문제 파악예전 트리 부모 찾기  문제랑 비슷한 맥락이다.인접리스트를 사용해서 풀었고 BFS를 활용했다.  개수가 아닌 순서이므로 들렸으면 +1 씩 해줘야 한다. 그래서 인접리스트의 한 배열을 방문한 후에 순서를 +1 하도록 코드를 짰다.그리고 문제에서 내림차순으로 방문한다고 했으므로 인접리스트의 한 배열을 방문하기 전에 인접리스트를 내림차순하고 돌아가도록 코드를 구성했다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색정렬  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m, r = map(int, input().split())graph = [[] * (n+1) for _ in range(n+1)]visited = [0..

✏️ 문제 문제 파악상하좌우 4가지가 붙어있으면 하나의 무리가 되므로 다음과 같이 방향 배열을 구성했다.d = [(1, 0), (0, 1), (-1, 0), (0, -1)] 무리의 개수를 구하는 것이므로 BFS가 한 무리를 돌 때마다 +1 하면 무리의 개수가 나온다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinefor _ in range(int(input())): h, w = map(int, input().split()) graph = [[0] * w for _ in range(h)] visited = [[0] * w for _ in range(h)] d = [(..

✏️ 문제 문제 파악문제를 읽어봤을 때 방향이 정해졌을 시 그 방향으로 칸에 적혀있는 수만큼 움직일 수 있는 것 같았다. 그래서 다음과 같이 코드를 짰다.다음 x위치 = 현재 x위치 + (움직일 방향 * 현재 밟고 있는 칸에 쓰여 있는 수)다음 y위치 = 현재 y위치 + (움직일 방향 * 현재 밟고 있는 칸에 쓰여 있는 수)  다음 x, y 위치가 -1일 경우 1을 리턴하고 끝까지 만나지 못할 경우 0을 리턴하여 이 리턴값을 기준으로 출력하는 문자열을 달리하였다. 알고리즘구현브루트포스 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())graph =..

✏️ 문제 문제 파악글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각하므로 다음과 같이 방향 배열을 구성했다.d = [(-1, 0), (0, 1), (1, 0), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1)] 글자의 개수를 구하는 것이므로 BFS가 한 번 돌면 한 글자이므로 돌 때마다 +1 하면 글자의 개수가 나온다.알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequem, n = map(int, input().split())graph = [[0] * n for _ in range(m)]visited = [[0] * n for _ in range(m)]d ..

✏️ 문제 문제 파악최소한의 이동 횟수를 출력하라 했으므로 BFS를 사용하여 푼다.동규가 현재 위치에서 다음 위치로 갈 수 있는 방법은 8가지가 있다.현재 위치 - 1현재 위치 + 1현재 위치 - A현재 위치 + A현재 위치 - B현재 위치 + B현재 위치 * A현재 위치 * B현재 위치에서 위 8가지의 다음 위치를 덱에 넣는 방법은 다음과 같다.for next_v in (v-1, v+1, v-a, v-b, v+a, v+b, v*a, v*b): q.append(next_v) 이렇게 for 문을 만들면 next_v에 8가지의 v의 다음 위치가 차례대로 대입하게 된다. 처음엔 graph와 visited 배열의 크기를 주미의 위치까지만 만들었는데 생각해보니 주미의 위치보다 더 멀리갔다가 다시 돌아오는 경..