알고리즘
-
BOJ 14546 Prison Break(Python 3)알고리즘/BOJ 2019. 1. 22. 11:11
https://www.acmicpc.net/problem/14546 문제 설명을 대충 해보자면 +오두막으로 처음 들어왔을 때는 인접한 +오두막으로만 이동할 수 있고, *오두막으로 들어왔을 때는 인접한 *오두막으로만 이동해서 탈출하는 문제이다. 전형적인 BFS 문제이고, BFS를 어떻게 구현하느냐 보다 좌표가 왼쪽 아래에서 (1,1)로 시작하고, (행,열)좌표가 아닌 (열,행)으로 뒤바뀌어져 있어서 좌표를 어떻게 입맛에 맞게 바꿀지 생각하는게 더 어려운 문제였다. 총 두 가지 방법을 사용할 수 있는데 간단한 방법은 위에서 아래로 뒤집는 것이다.뒤집는다면 (y,x)를 (y,n-x+1)로 표현할 수 있고, 배열은 (1,1)이 아닌 (0,0)으로 시작하므로 (y-1,n-x)로 바꾼 후, 좌표를 뒤집어 (행,열)..
-
BOJ 3055 탈출(Python 3)알고리즘/BOJ 2019. 1. 21. 15:33
https://www.acmicpc.net/problem/3055 BFS를 두번 돌리는 문제이다.이전에 화산쇄설류와 같은 유형의 문제이다.물의 이동을 먼저 BFS로 돌리고, 그다음 민혁이의 이동을 BFS로 돌린다.이때, 민혁이가 어떤 좌표 x에 가려고 한다면 물이 x에 도착하는 시간보다 빨라야 이동할 수 있다. 해당 부분만 유의하면 충분히 맞을 수 있는 문제이다. 코드확인 12345678910111213141516171819202122232425262728293031323334from collections import dequer,c=map(int,input().split())S=[input() for _ in range(r)]dx,dy=[0,0,1,-1],[1,-1,0,0]water_D=[[-1]*c ..
-
BOJ 16441 아기돼지와 늑대(Python 3)알고리즘/BOJ 2019. 1. 21. 14:25
https://www.acmicpc.net/problem/16441 이 문제에서 어려운 부분이 늑대가 빙판길에서 이동하는 방법과 중복 확인을 하는 방법을 처리하는 것인데, 나는 중복 체크 때문에 애를 좀 먹었다. 초원은 일반 상하좌우 BFS를 이용해 구현하였고, 빙판에 있을 때는 while문을 이용해 늑대를 계속 이동시키다가 맵의 범위를 넘어가거나, 산에 있을 때 값을 한번 빼서 바로 전에 이동한 값을 방문한 것으로 만들고, 빙판길을 가다가 초원이 나왔을 경우 바로 while 문을 빠져나와서 초원을 방문한 것으로 만들었다.이러면 빙판이 교차할 때 늑대가 갑자기 멈춰버리는 일도 없으니 문제를 해결 할 수 있을 것이다. 필자는 질문 글에 있는 반례도 맞던데, 제출하면 틀렸다고 나와서 머리 싸매다가 반례를 하..
-
BOJ 12273 Dragon Maze(Python 3)알고리즘/BOJ 2019. 1. 21. 13:54
https://www.acmicpc.net/problem/12273 간단한 BFS문제이다. 그냥 음수값만 피하면서 이동시키며 BFS를 돌리고, 도착점에 도착하면 파워의 최대값을 계속 갱신할 수 있도록 만들면 된다.비슷한 문제로는 '녹색 옷을 입은 얘가 젤다지?','군대탈출하기' 정도가 있다. 17~18줄 코드는 if문을 한 개로만 만들면 너무 길어서 가독성을 해칠 수가 있으므로, 두 개의 if로 나누어서 만들었다. 이 문제를 풀 수 있으면 Small도 풀 수 있으니 총 2문제나 풀 수 있으므로 매우 착한 문제이다. 코드확인 1234567891011121314151617181920212223from collections import dequedx,dy=[0,0,1,-1],[1,-1,0,0]Max=10000..
-
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,..