조준장 개발자 생존기

문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - deque가 아닌 heapq를 통해 리스트를 추가하여 각 정점을 탐색한다. - 각 정점에서 연결되어 있는 다른 정점을 확인하고 그 정점까지 걸린 거리를 비교하여 최단 경로를 초기화 한다. - 초기화 했다면 정점까지 걸린 거리와 정점의 번호를 리스트에 푸시한다. 코드 import sys from collections import deque import heapq # bfs 탐색 ..

문제 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 반복문을 통해 모든 친구를 기준으로 탐색한다. - 친구 관계를 확인하고 탐색하지 않은 친구라면 탐색한다. - 탐색하면서 탐색하기까지 걸린 횟수를 체크한다. - 케벤 베이컨의 수가 가장 작은 사람을 인덱스를 이용해서 출력한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(v): queue = d..

문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 알고리즘 - dfs 탐색을 통해 문제를 수행한다. - 제거할 노드를 정의한다. - 제거할 노드와 연결되어있는 리프 노드를 재귀함수를 통해 다시 제거할 노드를 찾는다. - 반복문을 통해 제거할 노드가 아니고 리프 노드가 없다면 카운트한다. 코드 import sys sys.setrecursionlimit(10 ** 6) # dfs 탐색 def dfs(delete): # 제거할 노드를 -2로 정의 tree[delete] = -2 # 반복문을 통해 제거할 노..

문제 1245번: 농장 관리 첫째 줄에 정수 N(1

문제 2823번: 유턴 싫어 상근이는 여자친구와의 드라이브를 위해서 운전을 배우고 있다. 도로 연수를 10년쯤 하다 보니 운전은 그럭저럭 잘하게 되었다. 하지만, 그는 유턴을 하지 못한다. 10년동안 도로 연수를 받았지 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 길의 좌표를 확인 후 하나의 길 좌표를 탐색한다. - 모든 길은 연결되어있기 때문에 하나의 길만을 탐색하여 연결된 길을 탐색하면 된다. - 4가지 방향에 길의 수를 체크하여 길의 개수가 2 미만일 경우 1을 리턴 받는다. - 모든 길을 탐색하면 0을 리턴 받는다. 코드 import sys from collections import deque def bfs(v): dx = [1, -1, 0, 0] dy = [..

문제 17204번: 죽음의 게임 중앙대학교 소프트웨어대학 새내기들을 맞이하게 된 17학번 김영기는 두 학번이라는 차이를 극복하기 위해 새내기들과 친해지려고 노력하고 있다. 그 노력 중 하나는 바로 새내기들과의 술자 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 사람의 수만큼 반복하여 탐색한다. - 탐색하는 번호가 보성이의 번호이면 현재 지목 횟수를 리턴 받는다. - 사람 수만큼 지목이 끝난 후에도 보성이의 번호를 탐색하지 못했다면 -1을 리턴 받는다. 코드 import sys from collections import deque # bfs 탐색 def bfs(v): queue = deque([v]) cnt = 0 # 사람의 수만큼 반복하여 지목한 사람을 확인 for _..

문제 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 치환까지 걸린 횟수를 방문 여부를 통해 확인한다. - b번 문자까지 걸린 탐색 횟수를 리턴하여 답을 출력한다. - 여기서 첫 번째에 카운트한 1을 빼줘 출력한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(): # a 번부터 탐색 queue = deque([a]) visited[a] = 1 # 큐..

문제 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 알고리즘 - dfs 탐색을 통해 문제를 수행한다. - 케이스만큼 반복하여 양의 무리를 출력한다. 코드 import sys sys.setrecursionlimit(10 ** 6) # 재귀 허용 깊이를 수동으로 늘려주는 코드 # dfs 탐색 def dfs(x, y): if x = h or y = w: return False # 탐색하지 않았다면 탐색 if graph[x][y] == "#": # 탐색 확인 graph[x][y] = "." # 양..

문제 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 총 6가지의 경우의 수를 가지고 탐색한다. - 물의 총량이 고정이기 때문에 a, b 두 물통만 체크하여 c 물통의 물의 양을 계산한다. - a 물통이 비어있는 경우에 c 물통에 남아있는 물의 양을 저장한다. 코드 import sys from collections import deque # a 물통과 b 물통의 경우의 수 저장 def pour(x, y): if not visited[x]..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 알고리즘 - bfs 탐색으로 문제를 수행한다. - 0부터 고속도로의 길이까지 반복하여 최단 거리를 구한다. - 지름길로 간 거리와 고속도로로 간 거리를 비교하여 최단 거리를 입력한다. - 지름길을 반복하여 최단 거리를 찾는다. 코드 import sys n, d = map(int, sys.stdin.readline().split()) graph = [list(map(int, input().split())) for _ in range(n)] dis ..