Problem Solving3 [Python] 2644 촌수계산 https://www.acmicpc.net/problem/2644 풀이#BFS #Graph아래와 같은 논리로 설계했다.자식 - 부모를 나타내는 번호를 그래프 상에서 잇는다. 한 번호 -> 다른 번호까지 거쳐가는 간선의 수가 가장 짧은 거리만큼 = 촌수!즉, 인접 리스트로 그래프를 표현하고, BFS로 최단 거리를 구하자BFS와 최단거리?BFS는 먼저 발견된 경로가 최단 경로임을 보장한다. 이는 BFS가 레벨별로 순차적으로 탐색을 진행하기 때문에, 먼저 도달한 노드가 최소한의 레벨임이 보장됩니다. 즉 가장 짧은 경로를 통해 도달한 것임을 의미하게 된다.* 반대로 최장거리를 구하자면, DFS를 이용하면 된다! 짚고 넘어가기✔️ BFS에서 queue에 원소를 add할 때 cnt 값도 같이 넣어, 현재 레.. 2024. 9. 7. [Python] 1449 수리공 항승 https://www.acmicpc.net/problem/1449 풀이#Idea #그리디붙여야할 곳으로 범위를 정해놓고, 그 범위에 해당하는지 검사하며, 해당할 시 continue, 해당하지 않을 시 테이프를 붙이기!범위는 리스트 각 원소들에 대해, start + 길이 로 표현하였다.처음에 범위 설정에 대한 개념을 생각하지 못했음.# 범위를 바꿔가며, 해당 범위에 있는지 검사!!import sysn, l = map(int, sys.stdin.readline().split())pipe = []pipe = list(map(int, sys.stdin.readline().split()))pipe.sort()start = pipe[0]cnt = 1for x in pipe[1:]: # 현재 범위에 해당한다면 co.. 2024. 8. 24. [Python] 2667 단지번호붙이기 풀이 #BFS 각각의 집 별로 상하좌우를 검사해야 한다. 검사했다면 해당 집의 상하좌우를 검사해가고.. 또 해당 집 주변을 검사.. 없다면 이전 식으로 돌아가기 -> 이를 반복 즉 모든 집에 대해 각각 상하좌우를 검사하자 -> 전수 검사 중 BFS or DFS! -> BFS를 선택 검사한 집은 0으로 바꾸어 다시 방문하지 않도록 하기 BFS로 한 단지내의 모든 집을 검사, 한 단지(=고립된 한 그래프) 검사 끝나면 BFS 종료됨 => 단지 리스트에 해당 집 수를 추가하기 이후 지도(maps)에서 1이 남아있는 집을 검사하고, 존재할시에 BFS를 호출하여 검사 from collections import deque # 1. 입력을 이중리스트에 저장하기 n = int(input()) maps = [] # ma.. 2024. 3. 21. 이전 1 다음
