본문 바로가기

BFS55

[백준 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.
[백준 1043번] 거짓말 https://www.acmicpc.net/problem/1043import sys from itertools import permutations from collections import deque input = sys.stdin.readline # 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다 # 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다 # 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다 # 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것 # 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다 # 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 .. 2024. 7. 10.
[백준 2660번] 회장뽑기 https://www.acmicpc.net/problem/2660import sysfrom collections import dequeinput = sys.stdin.readline# 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다# 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.# 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점# 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구# 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구# 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이# 회장의 점수와.. 2024. 7. 9.
[백준 24444번] 알고리즘 수업 - 너비 우선 탐색 1 https://www.acmicpc.net/problem/24444import sysinput = sys.stdin.readlinefrom collections import deque# N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다# 정점 번호는 1번부터 N번, 모든 간선의 가중치는 1# 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력n, m, r = map(int,input().split())graph = [[] for _ in range(n+1)]visited = [0]*(n+1)for _ in range(m): u, v = map(int,input().split()) graph[u].append(v) .. 2024. 7. 2.
[백준 11559번] Puyo Puyo https://www.acmicpc.net/problem/11559import sysfrom collections import dequeinput = sys.stdin.readline# 필드에 여러 가지 색깔의 뿌요를 놓는다# 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.# 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다# 이때 1연쇄가 시작된다.# 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.# 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마.. 2024. 7. 1.
[소프티어 6281번] 동계 테스트 시점 예측 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.aiimport sysfrom collections import dequeinput = sys.stdin.readline# 아침에 출근해보면 테스트 차량들 위에 눈얼음이 생겨있음# 커다란 얼음이 녹고난 뒤에 테스트가 가능# 차량마다 당일의 테스트 가능 시점을 알기 위한 예측 프로그램 제작# N x M 크기의 격자 위에 눈 얼음의 모양을 작은 정사각형들이 집합되어 있는 모양으로 변환# 아침이 되면 기온이 상승하여 천천히 녹는다# 얼음은 상하좌우 중에서 적어도 2변 이상이 외부와 접촉했을 때 정확히 1시간만에 녹음# 얼음 내부에 있는 공간은 얼음 외부 공기와 접촉하지 않는 걸로 가정# 주어진 얼음이 모두 녹아서 사라지는데 걸리는 시간n, m =.. 2024. 6. 27.

티스토리툴바