문제 백준 20183 골목 대장 호석 - 효율성2 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/20183 20183번: 골목 대장 호석 - 효율성 2 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 풀이 처음에는 dfs로 도전했지만 시간초과 문제를 해결 못했고, 다익스트라로 해결하기로 했다. 이진탐색으로 mid가 최대값이라고 가정했을 때 갈 수 있는가 판단해서 찾는다. import heapq import sys input=sys.stdin.readline n,m,a,b,c=map(int..

문제 백준 20955 민서의 응급 수술 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 풀이 이런 3개의 집합들을 연결하기 전에 사이클이 있는지 확인한 후에 사이클이 있는 집합에서 한 선만 제거하면 사이클이 사라지게 되므로 사이클이 있을 때 cnt를 하나씩 증가시킨다.(cnt만큼 제거 된다고 치는 것) 그리고 이제 한 노드씩 확인해서 부모가 다르다면 union 해주고 연결된 선(link)를 하나씩 증가시킨다. 예시를 정답으..

문제 백준 4963 섬의 개수 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 일단 보통 문제는 4방향으로 dx, dy를 지정하지만 이 문제는 대각선도 연결된 것으로 보므로 8방향으로 초기화해야 한다. 입력을 다 받고나서 탐색을 진행하는데 1인 부분을 찾을 때마다 dfs를 이용하고 방문처리를 진행한다. from collections import deque import sys sys.setrecursionlimit(..

문제 백준 13565 침투 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 풀이 맨 윗줄이 0인 부분만 q에 먼저 담고 bfs를 돌려서 맨 밑줄(index:m-1)에 도달한다면 멈춘다. from collections import deque m,n=map(int,input().split()) dx=[0,1,0,-1] dy=[1,0,-1,0] arr=[] visited=[[False]*n fo..

문제 백준 11085 군사 이동 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 풀이 union을 이용했는데 전기가 부족해 등의 문제는 최소값부터 연결해야 했다면 이 문제는 최대 부터 연결하여 연결하다가 Baekjoon World와 Cube World의 부모값이 같아진다면 그 때 연결한 값이 연결된 값중 최소 값이다. 코드를 보면 최대부터 연결하기 위해 최대힙을 이용했다. ..

문제 백준 12757 전설의 JBNU 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net 풀이 주석에도 적었지만 key들을 저장하는 keys리스트를 선언했는데 넣을 때부터 정렬하여 넣는다. 이때 이분 탐색을 사용하여 삽입했다. findkey 함수는 k값안에 내가 원하는 key가 있는지 확인하는 것인데, -2를 리턴할 때는 양쪽에 같은 k범..