알고리즘/BOJ
-
BOJ 12851 숨바꼭질2(Pyhton 3)알고리즘/BOJ 2019. 1. 21. 11:26
https://www.acmicpc.net/problem/12851 개인적으로 숨바꼭질3 보다 어려운 문제같다. S[x][0]은 가장 빠른 시간을 구하는 요소이고, S[x][1]은 경우의 수를 모두 구하는 요소로 다차원 배열을 만들었다.x는 이전에 있던 좌표, nx는 수빈이가 이동하는 좌표이다. if를 사용해서 수빈이가 처음 와본 좌표라면 경우의 수를 바로 이전에 있던 좌표의 경우의 수와 같게 해주고,(S[nx][1]=S[x][1])elif를 이용해 수빈이가 이미 와본 좌표이지만, 도달하는 시간이 같다면 원래 그 좌표에 저장해두었던 경우의 수에 이전에 있던 좌표의 경우의 수를 더해주었다.(S[nx][1]+=S[x][1]) 코드확인 12345678910111213141516171819from collect..
-
BOJ 1697 숨바꼭질(Python 3)알고리즘/BOJ 2019. 1. 21. 11:05
https://www.acmicpc.net/problem/1697 간단한 BFS문제이다. 이동하는 방법이 전부 1초라서 딱히 설명할 부분이 없다. 11줄 for문을 if 3개로 구현하는 분들이 있던데 이경우 코드 가독성이 너무 떨어집니다.(다른 BFS문제도 마찬가지)특히 자바는 가뜩이나 긴데, 질문글에 올린 자바 코드를 볼 때마다 너무 고통스러워요ㅠㅠ불가피한 상황이 아니라면 for문을 꼭 애용합시다. 코드확인 1234567891011121314from collections import dequeN,K=map(int,input().split())Max=10**5D=[-1]*(Max+1)D[N]=0q=deque()q.append(N)while q: x=q.popleft() for nx in [x-1,x+1,..
-
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())..