본문 바로가기

Algorithm 💡/BFS42

[백준 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.
[소프티어 6281번] 동계 테스트 시점 예측 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.aiimport sysfrom collections import dequeinput = sys.stdin.readline# 아침에 출근해보면 테스트 차량들 위에 눈얼음이 생겨있음# 커다란 얼음이 녹고난 뒤에 테스트가 가능# 차량마다 당일의 테스트 가능 시점을 알기 위한 예측 프로그램 제작# N x M 크기의 격자 위에 눈 얼음의 모양을 작은 정사각형들이 집합되어 있는 모양으로 변환# 아침이 되면 기온이 상승하여 천천히 녹는다# 얼음은 상하좌우 중에서 적어도 2변 이상이 외부와 접촉했을 때 정확히 1시간만에 녹음# 얼음 내부에 있는 공간은 얼음 외부 공기와 접촉하지 않는 걸로 가정# 주어진 얼음이 모두 녹아서 사라지는데 걸리는 시간n, m =.. 2024. 6. 27.
[소프티어 6282번] 장애물 인식 프로그램 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.aiimport sysfrom collections import deque# 1 - 장애물, 0 - 도로# 장애물 블록수 + 각 블록에 속하는 장애물의 수를 오름차순으로 정렬input = sys.stdin.readlinedx, dy = [-1,1,0,0], [0,0,-1,1]N = int(input())area = [list(map(int,list(input()))) for _ in range(N)]visited = [[False]*N for _ in range(N)]answer = []def bfs(x,y): queue = deque([(x,y)]) visited[x][y] = True count = 1 whi.. 2024. 6. 16.
[백준 5014번] 스타트링크 # 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있다# 스타트링크가 있는 곳의 위치는 G층이다# 강호가 지금 있는 곳은 S층# 엘리베이터는 버튼이 2개밖에 없다# U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼# (만약 U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)# 강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램# 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력from collections import dequeF, S, G, U, D = map(int,input().split())visited = [False]*1000001answer = float("inf").. 2024. 6. 9.
[백준 2636번] 치즈 https://www.acmicpc.net/problem/2636 # 판의 가장자리에는 치즈가 놓여 있지 않다.# 치즈에는 하나 이상의 구멍이 있을 수 있다.# 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다.# 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.# 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램from collections import dequedx = [-1,1,0,0]dy = [0,0,-1,1]r, c = map(int,input().split())area = [list(map(int,input().split())) for _ .. 2024. 6. 4.
[백준 4485번] 녹색 옷 입은 애가 젤다지? # 젤다의 전설 게임에서 화폐의 단위는 루피(rupee) # '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다 # 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다 # 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다 # 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다 # 링크가 잃을 수밖에 없는 최소 금액은 얼마일까? import sys from collections import deque input = sys.stdin.readline dx = [-1,1,0,0] dy = [0,0,-1,1] INF = float("inf") index.. 2024. 4. 22.

티스토리툴바