본문 바로가기
728x90

그래프64

[python] 백준 2660 회장뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 해결 전형적인 플로이드-위셜 문제 CODE import sys input = sys.stdin.readline INF = sys.maxsize n = int(input().rstrip()) dp = [[INF]*(n+1) for _ in range(n+1)] while True: a, b = map(int, input().split()) if a==-1 and b == -1 : break d.. 2023. 4. 9.
[python] 백준 2668 숫자고르기 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제 해결 사이클을 만들어서 사이클에 속해 있는 원소를 모두 가져올 수 있는지 확인하는 문제 사이클에 들어가는지 확인은 bfs, dfs 모두 가능하다.(하지만 문제에서 dfs를 원하는것 같다.) 이전에 풀어봤던 문제와 비슷하다.(무슨 문제였는지는 까먹어서...ㅜㅜ) CODE def cycle(num): global visited, c,result c.append(num) nx = gr.. 2023. 4. 7.
[python] 백준 16234 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 인구 이동이 진행될 때마다 계속 반복해서 진행하므로 시뮬레이션을 생각할 수 있다. 인구 이동 지역을 저장해야하므로 bfs를 이용해서 인구 이동 지역을 저장한후 평균을 그 지역 값에 넣어서 인구이동을 시킬 수 있다. 인구이동이 없으면 멈춰야한다. 이 부분에서 고민을 많이 했는데 이동한 지역이 없으면 인구 이동을 멈추는 변수 flag를 사용하여 인구 이동이 있으면 flag=1.. 2023. 4. 5.
[python] 백준 2583 영역 구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 해결 사각형으로 영역을 막아놓고 나머지 빈 구역의 개수를 구하고 각 영역의 크기를 구하면 되는 문제 bfs를 이용해 영역을 메우면서 쉽게 풀 수 있다. CODE from collections import deque def bfs(x,y): global visited que = deque() que.append((x,y)) visited[y][x] = 1 cnt = 1 dx.. 2023. 4. 4.
728x90