본문 바로가기

BFS55

[백준 16985번] Maaaaaaaaaze https://www.acmicpc.net/problem/16985# 5×5 크기의 판이 5개 # 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다.# 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. # 회전을 완료한 후 참가자는 판 5개를 쌓는다.# 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다.# 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로# 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸# 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸# 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.# 참가자 중에서 본인이 설계.. 2024. 10. 11.
[백준 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.
[백준 21609번] 상어 중학교 https://www.acmicpc.net/problem/21609# 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다.# 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현# 검은색 블록은 -1, 무지개 블록은 0으로 표현# 블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. # 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. # 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다.# 블록 그룹의 기준 블록은 무지개 블록이 아닌 .. 2024. 10. 1.
[백준 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.

티스토리툴바