알고리즘
-
BOJ 16569 화산쇄설류(Python 3)알고리즘/BOJ 2019. 1. 21. 10:50
https://www.acmicpc.net/problem/16569 t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다. 저 문장은 화산쇄설류가 1초마다 인접한 상하좌우로 퍼진다는 이야기이다. BOJ에 나온 탈출,불,불!과 같은 유형의 BFS 문제이다.먼저 화산쇄설류를 BFS로 돌리고, 그다음 재상이를 BFS로 돌리면 된다.재상이가 화산은 지나 갈 수 없다는 사실에 유의하며 문제를 풀면 된다. 코드1은 BFS를 다 끝낸다음, 마지막에 완전 탐색으로 높이의 최대값과 그때의 시간을 구했고, 코드2는 현재 BFS 돌리는 좌표가 h에 저장된 값보다 높으면 h와 t를 바로바로 갱신할 수 있도록 만들었다. 코드1 확인 123456789101112..
-
BOJ 16469 소년점프 (Python 3)알고리즘/BOJ 2019. 1. 21. 00:22
https://www.acmicpc.net/problem/16469 간단한 BFS 문제이다.deque를 이용해 넉살, 스윙스, 창모의 위치를 큐에 집어 넣어준다.R x C 배열에서 요소 하나에 3개의 값을 저장할 수 있는 다차원 배열 만들고, 넉살, 스윙스, 창모를 BFS 돌리면된다.세 악당이 모이는데 걸리는 최소 시간은 넉살, 스윙스, 창모가 어떠한 좌표 x에서 모일 때 가장 늦게 x에 도착한 사람의 시간을 구하면 된다. 파이참 색깔 그대로 올리면 좋을텐데 아쉽게도 흰색이 전부 회색으로 나온다. 코드확인 1234567891011121314151617181920212223242526272829303132from collections import dequen,m=map(int,input().split())..