백준4 [백준/Python] 11404번 플로이드 풀이최단 경로 알고리즘 중 하나인 플로이드 워셜 알고리즘으로 풀 수 있는 문제였습니다. 플로이드 워셜 알고리즘을 이해하고 있다면, 쉽게 풀 수 있는 문제였습니다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다 라는 것만 주의하시면 될 것 같습니다. import sysinput = sys.stdin.readlineINF = int(1e9)n = int(input())m = int(input())graph = [[INF] * (n + 1) for _ in range(n + 1)]for _ in range(m): a, b, c = map(int, input().split()) graph[a][b] = min(graph[a][b], c)for i in range(1, n+1): .. 2024. 8. 15. [백준/Python] 2667번 단지번호붙이기 풀이DFS, BFS 두 방법으로 풀 수 있는 문제였습니다. 저는 DFS 로 풀어보았습니다. 아래 코드에서 특정 x,y 좌표에서 dfs 함수를 한번 거치면, graph 상의 해당 x,y 좌표를 포함하여 상하좌우로 인접한 모든 1 을 0 으로 바꿉니다. 즉, dfs 함수를 한 번 거칠 때마다 아파트 단지수인 apart_complex 변수를 1 더해줍니다. 또, 그 과정에서 0으로 바꿀 때마다 단지내 집의 수를 구해주기 위해서 apart_unit 변수에 1 을 더해주는 작업을 합니다. 끝까지 탐색을 해주면, graph 의 모든 원소는 0으로 바뀌어 있을 겁니다. 1 이면 방문 해야하며, 0 이면 방문 완료 혹은 방문 하지 않아도 됨 입니다. import sysinput = sys.stdin.readlinen .. 2024. 8. 14. [백준/Python] 13706번 제곱근 풀이이분 탐색으로 양의 정수 N의 제곱근을 찾으면 됩니다. N의 길이가 800자리를 넘지 않는다는 것은 '10^800 - 1' 이 N의 최댓값이라고 볼 수 있습니다. N의 제곱근을 기준으로 이분 탐색을 할 것이기 때문에 '10^400' 을 N의 제곱근의 최댓값으로 잡고 이분 탐색을 하면 됩니다. (이보다 범위가 늘어난다 해도 이분탐색이기 때문에 탐색 속도에 큰 차이 없습니다.) 이분 탐색으로 N의 제곱근을 찾는거니까, mid의 제곱이 n 이 된다면 탐색 완료입니다. import sysn = int(sys.stdin.readline().rstrip())start = 1end = 10 ** 400while start mid ** 2: start = mid + 1 elif n 2024. 8. 8. [백준/Python] 17266번 어두운 굴다리 풀이이분 탐색을 통해 가로등의 높이를 찾아주면 됩니다. 가운데의 값(mid)이 굴다리 모든 길을 밝힐 수 있는 가로등의 높이라면 그 값을 result 변수에 저장해둔 뒤, 해당 값보다 더 작으면서 굴다리 모든 길을 밝힐 수 있는 또 다른 가로등의 높이를 찾기 위해 반복해줍니다. 그렇게 되면, 이분 탐색이 끝날 때는 result 에는 가장 값이 작으면서도 굴다리 모든 길을 밝힐 수 있는 가로등의 높이가 저장되어 있을 겁니다. 'canLight()' 함수는 가로등의 높이가 주어질 때, 해당 가로등의 높이로 굴다리 모든 길을 밝힐 수 있는 지 없는지 True, False 를 리턴해줍니다. 이 때, prev 변수는 이전 가로등이 비춘 최대 위치입니다. import sysn = int(sys.stdin.readl.. 2024. 8. 7. 이전 1 다음
