조준장 개발자 생존기

문제 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 사람마다 친구와의 관계를 bfs로 탐색한다. - 친구와의 관계가 2 미만인 경우만을 생각한다. - 각 사람마다 2-친구의 수를 구했다면 거기서 제일 유명한 사람을 출력한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(v): visited = [False] * n queue = deque([[v, 0]]) # 사람의 번호와 친구와의 관계 vis..

문제 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 알고리즘 - bfs 탐색과 다익스트라 알고리즘을 통해 문제를 수행한다. - 각 도시와 연결되어 있는 버스 노선을 확인하고 다음 도시까지 가는데 드는 비용을 비교하여 최소 비용을 초기화한다. 코드 import sys import heapq # bfs 탐색 def bfs(): heap = [] heapq.heappush(heap, [start, 0]) visited[start] = 0 while heap: x, y = heap..

문제 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] = "." # 양..