공부 기록

✏️ 문제 문제 파악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..

✏️ 문제 문제 파악동생을 찾는 "가장 빠른" 시간을 출력해야 하므로 BFS를 사용해야 한다.for 반복문을 이렇게도 사용하는 지 몰랐는데 다음과 같이 for 문이 주어지면 ( ) 안의 인자들은 탐색하려는 다음 가능한 위치들을 말한다.for a in (a - 1, a + 1, a + 2): ... 위와 같은 경우 첫 번째 반복에서 a 에 a - 1 이 할당되어 반복문이 진행된다. 예를 들어 a 가 5라면 이때 a 는 4가 된다.두 번째 반복에서 a 에 a + 1 이 할당되어 반복문이 진행된다. 예를 들어 a 가 5라면 이때 a 는 6가 된다.세 번째 반복에서 a 에 a + 2 이 할당되어 반복문이 진행된다. 예를 들어 a 가 5라면 이때 a 는 7가 된다.이 점을 활용하면 쉽게 문제를 풀 수 있다. 알..

✏️ 문제 문제 파악위와 같이 인접 리스트로 1과 연결된 6과 4, 2와 연결된 4 ... 이렇게 구현하려면 다음과 같이 append를 사용해야 한다.graph[a].append(b) 그리고 visited 배열에는 해당 인덱스의 부모 요소를 대입하여 후에 차례대로 출력하면 바로 결과값이 나오도록 구현했다. 알고리즘그래프 이론트리그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readline n = int(input())graph = [[] for i in range(n+1)]visited = [0] * (n+1) for i in range(n-1): a, b = map(int, input().split(..

✏️ 문제 문제 파악나는 visited 2차원 배열의 값을 세 가지로 나눠서 대입하고 이를 이용해 조건문을 구분하였다.0 → 방문 안한 섬1 → 방문한 섬-1 → 바다인 부분으로 방문하면 안되는 위치또한 이 문제의 경우 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 건너갈 수 있으므로 방향 배열을 다음과 같이 구성했다.d = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)] 아! 그리고 이 문제는 DFS로 풀 때 재귀를 사용해서 풀면 RecursionError 에러가 발생한다. 이는 Python이 정한 최대 재귀 깊이보다 내 코드의 재귀의 깊이가 더 깊어서 발생하는데 이를 해결하는 방법은 2가지가 있다.재귀 함수를 사용하지..

✏️ 문제 문제 파악처음엔 연결 요소가 뭐지 싶어서 검색해봤는데 많은 좋은 자료들이 있었다. (모르면 보고 오시길 추천!)문제의 예제1, 예제2를 그림 그려본다면 연결 요소의 개수는 다음과 같이 된다.처음 코드를 짤 땐 visited 배열을 1차원 배열로 줬는데 그러면 서로 연결되어 있다는 게 담기 어려웠다. (연결되어 있으면 1로 변경했을 시 1차원 배열이면 예제1의 경우 전부 1이 됨)그래서 2차원 배열로 구현하니 쉽게 풀 수 있었다! 아! 그리고 이 문제는 DFS로 풀 때 재귀를 사용해서 풀면 RecursionError 에러가 발생한다. 이는 Python이 정한 최대 재귀 깊이보다 내 코드의 재귀의 깊이가 더 깊어서 발생하는데 이를 해결하는 방법은 2가지가 있다.재귀 함수를 사용하지 않고 스택으로 ..

✏️ 문제 문제 파악집이 모여있는 곳을 모두 접근해야 하므로 깊이 우선 탐색을 사용해서 풀었다.그리고 단지 개수를 세야 하므로 깊이 우선 탐색을 돌 때마다 개수를 +1 해주었고 깊이 우선 탐색에 단지 번호를 매개 변수로 주어 풀었다. 여기서 나는 visited 2차원 배열에 조건을 주었는데0 → 방문 안해도 되는 거1 → 방문한 거-1 → 방문해야 되는데 아직 방문 안한 거이렇게 세 가지로 나눠서 조건문을 구분하였다. 예제를 넣었을 때는 잘 풀렸는데 틀렸다고 나온다면 각 단지내 집의 수를 단지 번호 차례대로가 아닌 각 단지내 집의 수를 오름차순으로 출력했는지 확인해보아야 한다! (내 얘기) 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드n = int(input())d = [(-1, 0..

✏️ 문제 문제 파악배추들이 모여있는 곳을 모두 접근해야 하므로 깊이 우선 탐색을 사용해서 풀었다.그리고 배추들이 모여있는 곳 당 한 마리씩 필요하므로 깊이 우선 탐색을 돌 때마다 개수를 +1 해주면 된다. 여기서 나는 visited 2차원 배열에 조건을 주었는데0 → 방문 안해도 되는 거1 → 방문한 거-1 → 방문해야 되는데 아직 방문 안한 거이렇게 세 가지로 나눠서 조건문을 구분하였다. 아! 그리고 이 문제는 DFS로 풀 때 재귀를 사용해서 풀면 RecursionError 에러가 발생한다. 이는 Python이 정한 최대 재귀 깊이보다 내 코드의 재귀의 깊이가 더 깊어서 발생하는데 이를 해결하는 방법은 2가지가 있다.재귀 함수를 사용하지 않고 스택으로 DFS 구현sys.setrecursionlimit..

✏️ 문제 문제 파악처음 바이러스에 걸린 컴퓨터와 인접된 모든 컴퓨터를 돌아야 하므로 BFS가 아닌 DFS를 사용해서 풀어야 한다. # 1graph = [[0] * (c+1)] * (c+1) graph[1][2] = 1print(graph)# [[0, 0, 1, 0],# [0, 0, 1, 0],# [0, 0, 1, 0],# [0, 0, 1, 0]]# 2graph = [[0] * (c+1) for _ in range(c+1)]graph[1][2] = 1print(graph)# [[0, 0, 0, 0],# [0, 0, 1, 0],# [0, 0, 0, 0],# [0, 0, 0, 0]] 처음 graph 2차원 배열을 초기화할 때 # 1 과 같이했는데 원하는 값이 계속 안나왔다.  찾아보니 # 1 과 ..

✏️ 문제 문제 파악최소의 칸 수를 출력하기 원하므로 전체 경로를 탐색하는 DFS가 아닌 BFS를 사용해야 한다. 또한 상하좌우로 움직일 수 있으므로 상하좌우 하나하나 움직이며 움직인 좌표가 이동할 수 있는 칸인 지, 이미 방문했던 칸은 아닌 지 확인하는 것이 포인트이다. 처음에는 단순히 지나간 칸마다 cnt += 1을 해서 cnt 값을 출력하는 방식으로 문제를 풀었다. 그런데 생각해보니 지나간 칸이더라도 그 이후에 갈 수 있는 경로가 없다면 그 칸을 문제에서 요구하는 최소 칸 수에 포함시키면 안 된다. 그래서 이전의 방문한 칸에 이때까지 지나왔던 칸의 수를 1씩 더하니 답이 나왔다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드import sysinput = sys.stdin.readlinefr..

DFS (깊이 우선 탐색) 와 BFS (너비 우선 탐색) ?그래프 탐색 알고리즘의 대표적인 예로 이 알고리즘들은 그래프, 트리, 네트워크 등의 자료구조를 탐색하는 데 사용한다. 그래프는 노드(정점)와 노드 간의 연결선(간선)으로 이루어진 자료구조를 말한다.노드 (Vertex) : 그래프에서 하나의 개체를 말하며 정점이라고도 한다.간선 (Edge) : 두 노드를 연결하는 선인접 노드 : 특정 노드와 직접 연결된 노드DFS (깊이 우선 탐색)시작 노드에서부터 한 방향으로 갈 수 있을 만큼 깊이 내려가며 탐색을 진행한다. 그 깊이의 노드를 모두 탐색한 후 더 이상 갈 수 없게 되면 이전 정점으로 돌아가 다음 노드를 탐색하는 방식이다. 탐색 과정시작 노드에서 출발하여 다음 노드로 이동더 이상 방문하지 않은 인..