그래프

[python] 백준 - 1012. 유기농 배추

🤔문제 해결 S2 | 그래프, DFS 배추밭과 배추의 위치를 2차원배열로 만든다. 배추리스트에서 하나 꺼내서 DFS로 인접한 배추들을 다 0으로 바꿔준다. 💻소스 코드 import sys input = sys.stdin.readline def find_dummy(x: int, y: int): farm[x][y] = 0 stack = [(x, y)] dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] while stack: cx, cy = stack.pop() for k in range(len(dx)): nx = cx + dx[k] ny = cy + dy[k] if 0

[python] 백준 - 1325. 효율적인 해킹

🤔문제 해결 S2 | 그래프, BFS(DFS) 단순한 그래프 문제였는데 전부다 시간초과 발생.... 다른 분들 제출한것도 보니까 대부분 시간초과이다. (그래서 pypy3로 제출하니 성공) 풀이방법은 인접리스트 생성 (이 문제에서는 a->b가 아니라 b->a 이다) 모든 노드에 대해서 BFS를 돌린다. 그 때 몇개의 노드를 돌았는지 숫자를 세준다. 가장 높은 카운트의 노드들을 출력한다. 다른 분들의 풀이를 봤는데 풀이가 나랑똑같다. 하지만 어떻게 통과했는지... 💻소스 코드 import sys from collections import defaultdict from collections import deque def bfs(start): q = deque([start]) visited = [0] * (N ..

다익스트라(dijkstra)

📔 다익스트라(dijkstra) 란 다익스트라를 들어가기 전에... 최단 경로란 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 간선의 가중치가 균일(1)할 경우 BFS를 사용 음의 가중치를 허용하지 않음 하나의 시작 정점에서 끝 정점까지의 최단경로 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 시작 정점(s) 에서 끝 정점(t) 까지의 최단 경로에 정점 x 가 존재한다. 이때, 최단 경로는 s 에서 x 까지의 최단경로와 x 에서 t 까지의 최단경로로 구성된다. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다. 아래 코드의 경우 시간복잡도는 O(N^2) 이다. 만약 우선순위큐를 이용하게 된다면 O(NlogN..

[python] 백준 - 7562. 나이트의 이동

🤔문제 해결 S2 | BFS BFS로 다 돌아주다가 도착지를 만나면 끝! 💻소스 코드 from collections import deque def bfs(): q = deque() q.append((start_x, start_y)) while q: cx, cy = q.popleft() if cx == end_x and cy == end_y: print(chess[cx][cy]) return for k in range(len(dx)): nx = cx + dx[k] ny = cy + dy[k] if 0

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라, 그래프 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 알고리즘 간선, 최소 등등 말이 나오면 다익스트라? 나의 경우 다익스트라를 풀 때 항상 우선순위 큐를 이용한다. (파이썬의 힙큐를 사용) A 에서 갈 수 있는 모든 정점들의 최소비용을 리스트에 담아두고 B 지점을 답으로 출력한다. 먼저 (가중치, 시작점)을 힙큐에 넣고 시작한다. 시작점에서 각 정점까지의 비용은 가장 큰 값(파이썬에서 float('inf')를 넣어두고 시작한다.) 힙큐에서 값을 하나씩 꺼낸다. 꺼낸 정점에서 이웃한 정점들 중에서 아직 방문하지 않았고, 이웃한 정점까지의 비용보다 현재비용 + 꺼낸 정점에서 이웃한 정점까지의 간선비용이 작으면 각 정점까지의 비용을 현재비용 + 꺼낸 정점에서 이웃한..

[python] 백준 - 16953. A → B

🤔문제 해결 S1 | 그래프, BFS 난 DFS 알고리즘 분류에는 그래프와 BFS로 나와있는데 잘 모르겠고, DFS로 해결했다. 목표 숫자부터 두가지 경우로 나눠서 들어간다. 맨 끝의 숫자가 1이면 1을 버리고 재귀 맨 끝의 숫자가 1이 아닐 때 2로 나누어 떨어지면 2로 나누고 재귀 테스트 케이스 3번을 예시로 하겠다 ( 100, 40021 ) 40021: 맨 끝의 숫자가 1이므로 1을 버린다 40021 => 4002 체크하는 방법은 10으로 나눈 나머지, 버리는 방법은 10으로 나눈 몫 4002: 맨 끝의 숫자가 1이 아니고 2로 나누어 떨어지므로 2로 나눈다. 4002 => 2001 2001: 버린다. 2001 => 200 200: 나눈다. 200 => 100 100: 100 == A 이므로 그만!..