전체 글
-
BOJ 13913 숨바꼭질4(Python 3)알고리즘/BOJ 2019. 1. 21. 13:20
https://www.acmicpc.net/problem/13913 문제 난이도에 비해 정답 비율이 높은 문제다. 이 문제를 다시 풀다보니 그동안 숨바꼭질 문제에서 굳이 필요하지 않은 코드가 있다는 것을 알고 수정하였다.(중복 확인 코드가 사실 필요 없다.) 이동 과정을 저장하는 방법은 2차원 리스트를 만들어서 D[nx][0]은 시간에 대한 값, D[nx][1]은 이전에 있던 좌표인 x를 저장하여 나중에 K를 구할 때 D[nx][1]을 보고 역추적 할 수 있도록 만들었다.N은 10, K는 80이라고 예시를 들어보면 10 -> 20 -> 40 -> 80 이라는 이동경로가 있을 때, D[80][1]엔 40이 저장되어 있을 것이고, D[40][1]은 20, D[20][1]은 10이 저장되어 있으니까 이 값을 ..
-
BOJ 13549 숨바꼭질3(Python 3)알고리즘/BOJ 2019. 1. 21. 12:25
https://www.acmicpc.net/problem/13549 숨바꼭질1과 비슷해 보이지만 0초 후에 2*X의 위치로 이동하게 된다는 내용으로 조건이 변경된 문제이다. 이 경우에는 X-1,X+1을 먼저 하는 것보다는 2*X로 이동할 수 있으면 전부 2*X로 이동시키고, 그다음 X-1,X+1로 이동시키면 된다. 코드1은 2*X로 이동시킬 때 collections.deque에 있는 명령어인 appendleft를 사용하였는데 appendleft는 큐의 맨 왼쪽으로 넣는 명령어이기 떄문에 bfs와 똑같이 popleft를 이용하면 된다. 코드2는 큐 자체를 덱이 아닌 리스트로 만든다음. heapq의 명령어인 heappush,heappop을 이용하여 bfs를 만들었다.heapq는 값을 계속 정렬해서 저장하기 ..
-
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())..