알고리즘/BOJ
-
BOJ 9019 DSLR(Python 3)알고리즘/BOJ 2019. 1. 22. 17:25
https://www.acmicpc.net/problem/9019 시간이 오래 걸리지 않는 문제였는데, 뒤집어서 출력해야 하는 것을 그대로 출력하는 것으로 계속 제출해서 연달아 틀렸습니다가 나온 문제다 코드 내부에 문제가 있는 줄 알아서 확인해보니 내 눈엔 문제가 없어보여서 코드를 수차례나 지우고 다시 쓰고를 반복했따 ㅠㅡㅠ DSLR은 숨바꼭질 4의 10% 업그레이드? 한 BFS 문제이다.나는 문자열로 L,R을 구현하면 시간 초과가 나왔는데, 다른 분이 하신 코드를 보니 문자열을 이용해서 L,R을 구현해도 통과를 할 수 있다. 출력은 숨바꼭질 4와 똑같이 역추적하는 리스트 하나를 만들어서 while문을 돌려서 한 줄의 문자열을 만든다음, 뒤집어서 출력을 하면 된다. 그리고 Python3은 매우 느리니 P..
-
BOJ 14948 군대탈출하기(Python 3)알고리즘/BOJ 2019. 1. 22. 12:40
https://www.acmicpc.net/problem/14948 말이 되고픈 원숭이의 BFS유형과 이전에 글을 올린 Dragon Maze의 BFS유형을 합친 문제이다. 푸는 방법은 특수 장비를 쓸 수 있는 기회가 한 번 있고, 출발점에서 도착점까지 최소 레벨로 이동할 수 있는 레벨을 구하는 것이다. 생각은 간단하지만 막상 만들려고 하면 생각보다는 좀 길어서 혹시나 틀릴 경우 코드를 꼼꼼히 봐야 한다. 조심해야 하는 경우가 총 3가지가 있다.1) 한 좌표 안에 특수 장비를 사용한 경우, 사용하지 않은 경우를 나눠서 값을 저장하기2-1) 특수 장비를 쓰지 않았을 경우, 다음 방향으로 이동할 때 특수 장비를 사용하지 않을 때와 사용할 때로 나눠서 이동시키기2-2) 특수 장비를 사용한 경우, 무조건 인접한 ..
-
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는 값을 계속 정렬해서 저장하기 ..