전체 글
-
BOJ 16724 피리 부는 사나이(Python 3)알고리즘/BOJ 2019. 1. 24. 10:13
https://www.acmicpc.net/problem/16724 문제 푸는 방식은 간단했지만, 이걸 생각해내는 과정이 참 힘들었던 문제다. 완전 탐색을 돌려서 아직 방문하지 못한 좌표를 만났다면 t+=1을 한 후에, 방문하는 좌표마다 숫자t로 체크해주고, 계속 이동하다가 만약 t로 체크된 좌표와 만났다면 SAFE ZONE을 하나 늘리고 함수를 종료하고(싸이클), 그게 아니라 t`(이전의 t)와 만나면 SAFE ZONE을 늘리지 말고 바로 함수를 종료하는 형식으로 해주었다. Q) 왜 t`를 만나면 SAFE ZONE을 하나 늘리지 않고, 바로 함수를 나가나요?(이해를 돕기 위한 그림) A) 만약 t`가 싸이클이라면 t로 색칠된 좌표에서 이동하다가 결국 t`로 이동해서 t`의 싸이클을 돌 것이고, t`에는..
-
BOJ 16174 점프왕 쩰리(Python 3)알고리즘/BOJ 2019. 1. 23. 15:16
이 문제는 Large와 Small 두 개를 한번에 맞을 수 있는 문제라 매우 좋은 문제다.BFS를 배우기 전에는 Small문제 가지고 모든 경우의 수를 파이썬에 만들었다가 틀려서 가슴이 아팠던 기억이 난다. 다이나믹으로 풀 수 있다.점프할 수 있는 곳이 범위를 초과하지 않을 때 점프하기 전의 위치에 있는 값을 더한다.그리고 n-1,n-1위치일 때는 for문을 종료하고 HaruHaru나 Hing을 출력한다. 아니면 BFS로 풀 수 있는데 그 코드는 문제집 카테고리에 들어가면 BFS / DFS / Dijkstra / Bellman-Ford 라는 글이 있는데, 거기에 BFS 소스 코드가 있습니다.(https://hello70825.tistory.com/86)BFS 코드를 보고 싶으면 거기 들어가서 확인하면 됩..
-
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..