본문 바로가기

Algorithm 💡/BFS42

[백준 2638번] 치즈 https://www.acmicpc.net/problem/2638import sysfrom collections import dequeinput = sys.stdin.readlinedx, dy = [-1,1,0,0], [0,0,-1,1]# 치즈는 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다# 각 치즈 격자(작은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다N, M = map(int,input().split())# 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시# 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정# 출력 : 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간area = [.. 2024. 10. 3.
[백준 17141번] 연구소 2 https://www.acmicpc.net/problem/17141# 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.# 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.# 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸# 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.# 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력# 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력import sysfrom collections import dequeinput = sys.stdin.readlineN, .. 2024. 10. 1.
[백준 1389번] 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389# 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결# 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임# 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람# 유저 중에서 케빈 베이컨의 수가 가장 작은 사람# 즉, 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합import sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int,input().split())graph = [set() for _ in range(n+1)]minimum = float("inf.. 2024. 9. 10.
[백준 6118번] 숨바꼭질 import sysfrom collections import dequeinput = sys.stdin.readline# 헛간의 개수는 N(2 maximum: answer = [v] maximum = depth elif depth == maximum: answer.append(v) for n in graph[v]: if not visited[n]: q.append((n,depth+1)) visited[n] = Truebfs()print(f"{min(answer)} {maximum} {len(answer)}") 본 문제는 N개의 노드와 .. 2024. 8. 6.
[백준 2234번] 성곽 https://www.acmicpc.net/problem/2234import sysfrom collections import dequeinput = sys.stdin.readline# 서 : 1# 북 : 2# 동 : 4# 남 : 8# 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로# 1.성에 있는 방의 개수# 2.가장 넓은 방의 넓이# 3.하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기# 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.dx, dy = [-1,1,0,0],[0,0,-1,1]n, m = map(int,input().split())visited = [[False]*n for _ in range(m)]area = [lis.. 2024. 7. 17.
[백준 2660번] 회장뽑기 https://www.acmicpc.net/problem/2660import sysfrom collections import dequeinput = sys.stdin.readline# 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다# 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.# 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점# 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구# 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구# 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이# 회장의 점수와.. 2024. 7. 9.

티스토리툴바