그래프17 [Python] 백준 16234번 : 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 문제 풀이 BFS를 기반으로 한 구현 문제이다. 문제에서 요구하는 답은 인구 이동이 몇 번 일어났는지가 아니라 인구 이동이 일어난 날짜이다. 따라서, 단순하게 몇번 실행되었는지 보다 날짜를 기준으로 카운트하는 게 중요하다 ✔️ 느낀 점 중요한 점을 놓쳐서 코드를 깨작깨작 계속 수정햇던 문제이다. 시간 복잡도는 생각한대로 해결되었다! 💻 코드 import sys ; input = .. 2023. 3. 6. [Python] 백준 15686번 : 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 💡 문제 풀이 기본적인 구현, DFS 문제이다. ✔️ 느낀 점 💻 코드 import sys from itertools import combinations input = sys.stdin.readline N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] chick.. 2023. 2. 27. [Python] 백준 1520번 : 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 💡 문제 풀이 그래프 탐색(DFS)에 DP를 곁들인 문제이다. 그냥 DFS로 구현하면 시간초과가 발생한다. 그래서 이미 지나온 길에 대해서는 이전에 방문한 결과를 바로 전달해 주는 방식으로 중간에 순회하는 시간을 줄일 수 있다. ✔️ 느낀 점 그냥 DFS 문제인 줄 알았지만 DP가 곁들인거 보고 큰코다쳤다. 💻 코드 import sys input = sys.stdin.readline dx = [.. 2023. 2. 26. [Python] 백준 17396번 : 백도어 https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 💡 문제 풀이 기본적인 다익스트라 문제이다. 추가적으로 특정 조건에 값을 추가할지 말지 확인하는 로직만 추가하면 된다. ✔️ 느낀 점 오타 나서 한참 찾았다.. 💻 코드 import heapq, sys INF = int(1e9) input = sys.stdin.readline def dijkstra(start): q = [] heapq.heappush(q, (0, sta.. 2023. 2. 25. [Python] 백준 1956번 : 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 💡 문제 풀이 플로이드-워샬 문제이다. 각 노드 사이의 최단거리를 구하고 만들어지는 사이클에 대한 최솟값을 구하면 된다 사이클은 단순히 시작점에서 목표 지점과 목표 지점에서 시작점을 접근할 수 있는지만 확인하면 된다.. 일방통행이라 다양한 경우를 따지지 않아도 괜찮다. ✔️ 느낀 점 중간에 사이클을 어떻게 고려할까 고민을 조금했는데 생각해 보면 간단한 문제였다. .. 2023. 2. 23. [Python] 백준 13023번 : ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 💡 문제 풀이 ✔️ 느낀 점 💻 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = [[] for i in range(n)] visited = [False] * n for _ in range(m): a, b = map(int, input().split()) arr[a].append(b) arr[b].append(a) def dfs(idx, number): if number == 4: print(1) exit() .. 2023. 2. 23. 이전 1 2 3 다음