Dev_Diary

https://www.acmicpc.net/problem/2638DFS / 그래프 탐색 문제입니다.주의할 점이 있다면 탐색과 동시에 치즈를 녹이는 작업을 병행하게 된다면 다음 탐색 시에 치즈가 녹은 위치를 바로 탐색하게 되어 실제 카운트에 영향이 있을 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, M, cz_map): # 이동 방향 move_dir = [[0, 1], [0, -1], [1, 0], [-1, 0]] # 카운트 cnt = 0 # 치즈가 남지 않을 때 까지 순회 while any([any(cz) for cz in cz_map]): # 방문 ..

https://www.acmicpc.net/problem/17142어떻게 시작 바이러스 위치를 샘플링 할까 고민하시겠지만 모든 경우를 진행해보면 됩니다. 최대 바이러스 10 개중 M 개를 뽑는 경우의 수 중 최대는 M == 5 인 경우일텐데 252 가지 밖에 안되기 때문에 모두 진행한다고 해도 최악의 경우 252*50*50 = 630,000 번의 계산이 일어납니다. 때문에 모든 경우를 계산해도 아주 넉넉하게 통과할 수 있습니다. M 개의 바이러스를 뽑았다면 모든 M 개의 점에서 동시에 BFS 를 진행하며 최솟값을 갱신해주면 됩니다.import sysfrom collections import dequefrom itertools import combinationsinput = sys.stdin.readlin..

https://www.acmicpc.net/problem/4179BFS 로 그래프를 탐색하는 문제입니다.다만 불과 사람이 동시에 움직이는데, 같은 위치에 동시에 있으면 사람은 이동 불가이므로 불 먼저 이동시켜주면 되겠습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(R, C, labyr): # 불 데크 fire_dq = deque() # 사람 데크 hum_dq = deque() # 사람 방문 목록 hum_visited = [[True for _ in range(C)] for __ in range(R)] # 미로 탐색하며 위치 체크 for i in range(R): ..

https://www.acmicpc.net/problem/15558BFS 를 사용하면 풀 수 있는 문제입니다.이동 가능한 모든 위치에 대하여 큐에 넣어주고 큐가 빌때까지 순회하면 됩니다.다만 발판이 하나씩 없어지는 점을 생각해 이동 횟수 - 1 의 인덱스를 갖는 발판을 지워주면 해결됩니다.import sysfrom collections import dequefrom copy import deepcopyinput = sys.stdin.readlinedef solution(N, K, data_list):    # 큐 / 인덱스, 이동 횟수    dq = deque([[[0, 0], 0]])    # 방문 목록    visited = deepcopy(data_list)    # 순회    while dq:  ..

https://www.acmicpc.net/problem/1520단순한 BFS, DFS 로 진행하면 시간초과가 발생합니다.그래서 한번에 모든 길을 찾는게 아닌 중간중간 가능한 경로를 합해주며 진행하겠습니다. A - B - C - D - E - FA - B - G - D - E - F 두 경로로 이동이 가능하다고 가정하면D 의 지점에서 D 까지 도달하는 경로를 병합한 뒤, D 에서 F 까지는 한 번만 탐색하는 방식입니다. 해당 방식을 구현하기 위해 DFS 와 heapq 를 사용했습니다.D 에서 탐색을 시작하기 전에 D 보다 높은 지점에서의 이동 먼저 계산하기 위함입니다.그러므로 heapq 안의 구성요소는 [높이, [인덱스]] 가 됩니다. 일반적으로 heapq 는 최소힙을 기본으로 하기 때문에 최대힙을 사용..

https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 선분이 교차하는지 판단하는 알고리즘과 그룹을 판단하기 위한 유니온 파인드 알고리즘을 함께 사용하면 풀 수 있습니다. 우선 선분이 교차하는지 판단하기 위해 두 개의 선분이 주어졌을 때 가질 수 있는 상태를 생각해보겠습니다. 위와 같이 열 가지의 상태가 존재하며 모든 상태를 고려해주겠습니다. 상태의 파악에는 CCW 알고리즘을 사용하겠습니다. (0, 0) 의 경우에는 ..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 전형적인 그래프 탐색 문제입니다. 다만 DFS 로 풀었다 시간초과가 발생해서 BFS 로 풀었습니다. from collections import deque def solution(n, field): # 맵 정리 start, field = field[0], field[1:] # BFS 로 풀거 que = deque([start]) # 방문 기록 visited = [1 for _ in range(..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제는 전형적인 그래프 탐색 문제입니다. BFS 와 DFS 중 적절하게 선택해 풀면 됩니다. # BFS 쓸거라 deque from collections import deque def solution(F, S, G, U, D): # 선택지 selects = [U, -D] # 방문한 위치 visited = [1 if floor != S else 0 for floor in range(F+1)] que = deq..