본문 바로가기
728x90

그래프64

[python] 백준 11562 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 문제 해결 graph[u][v] : u에서 v까지 가는데 필요한 양방향화 필요한 길 개수 처음에 INF로 정의한다음 연결되어있다고 입력값이 주어지만 graph[u][v] = 0 만약 양방향이 아니고 u→v는 연결이 되어있는데 v→u는 연결이 안되어있으면 graph[v][u] = 1로 정의 플로이드-위셜을 이용하여 필요한 양방향화 길의 개수를 구할 수 있다. 플로이드-위셜로 최소거리가 아닌 필요한.. 2024. 4. 3.
[python] 백준 16724 피리 부는 사나이 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 문제 해결 safe존을 어떻게 해야 최소로 만들 수 있는지 생각을 해봐야한다. 우선 순환하는 사이클이 있으면 하나를 무조건 만들어야한다는 생각을 가져야한다. 하지만 만약 다른 그룹으로 연결이 될 수 있는 경우도 있다. 예로들면 D L L R D Y U R U 다음과 같은 경우 사이클이 존재하면서 가장 왼쪽 아래있는 'U'는 사이클에 연결이 되므로 safe존은 하.. 2024. 3. 8.
[python] 백준 4386 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해결 전형적인 유니온 파인드 문제 단 리스트 안에 두 별자리 간의 거리를 오름차순으로 정렬하고 연결 되어있는지 아닌지 유니온 파인드를 통해 확인하고 해결한다. CODE import sys input = sys.stdin.readline import math def find(x): if x != parents[x]: return find(parents[x]) return parents[x] de.. 2024. 3. 7.
[python] 백준 14939 불 끄기 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 문제 해결 문제의 이해는 쉽지만 풀기 많이 어려웠던 문제 어디서부터 시작해야할지 많이 어렵다. 이 때 불 키고/끄고를 비트마스크를 이용해서 풀 수 있다고 하는데 어려워서 여러 코드를 확인하였다. 가장 중요한 것은 '첫 번째' 행의 불이 켜져있든 꺼져있든 스위치를 누루는 경우의 수를 모두 탐색하는 것이다. 이유는 첫 번째 행이 꺼져있어서 눌러 불을 켜도 다음 밑에 있는 스위치를 눌러서 다.. 2024. 3. 2.
728x90