알고리즘
-
BOJ 12886 돌 그룹(Python 3)알고리즘/BOJ 2019. 1. 29. 17:13
https://www.acmicpc.net/problem/12886 물통이랑 비슷한 문제입니다. A,B,C 중복 체크를 확인해주는 것만 생각하면 되는 문제입니다.A,B의 값을 알고 있다면 C를 구할 수 있으니 2차원 배열로 나타낼 수 있습니다.(2차원 배열 중복 확인은 A,B를 하든, B,C를 하든 입맛에 맞게 하면 됩니다.)저는 최솟값, 최댓값으로 중복 체크를 했습니다. 그리고 제 코드는 BFS를 돌리기 전에 A+B+C가 3의 배수가 아니면 0을 출력하고 종료하는 것으로 만들었는데, 이 부분은 BFS 돌리면서 A,B,C의 값이 같을 때 처리해도 무방합니다. 코드확인 123456789101112131415161718192021222324252627from collections import dequea,b..
-
BOJ 14497 주난의 난(難)(Python 3)알고리즘/BOJ 2019. 1. 25. 13:44
https://www.acmicpc.net/problem/14497 숨바꼭질3과 비슷한 문제이다. 주난이 상하좌우로 이동할 수 있다고 가정할 때, 친구가 있는 곳으로 이동하는데 1초가 걸리고, 빈 공간이 있는 곳으로 이동하는데 0초가 걸린다고 생각하면 된다. 빈 공간으로 이동할 때는 appendleft로 큐의 맨 왼쪽에 넣어주고, 친구가 있는 곳으로 이동할 때는 append를 이용해 큐의 오른쪽에 넣어준다. 숨바꼭질3을 푸는 방법처럼 heapq를 이용해서 풀어도 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from collections import deque n,m=map(int,input().split()) x1,y1,x2,y2=map(..
-
BOJ 7569 토마토(Python 3)알고리즘/BOJ 2019. 1. 25. 13:22
https://www.acmicpc.net/problem/7569 바로 이전 글에 있는 토마토 문제의 3차원 버전 문제이다. 여기에서 주의할 점은 M,N,H로 주어지는 값이 배열에서는 List[H][N][M] 이다. 이 부분만 유의해서 만든다면 2차원 토마토와 똑같은 문제이다. 코드확인 1234567891011121314151617181920212223242526from collections import dequem,n,h=map(int,input().split())D=[list(list(map(int,[*map(int,input().split())])) for _ in range(n)) for k in range(h)]dx,dy,dz=[0,0,0,0,1,-1],[0,0,1,-1,0,0],[-1,1,0,..
-
BOJ 7576 토마토(Python 3)알고리즘/BOJ 2019. 1. 25. 13:06
https://www.acmicpc.net/problem/7576 재미있는 BFS문제이다. 완전 탐색으로 1이 들어간 값을 전부 큐에 저장한 뒤에 BFS 돌리면 된다.이 문제에서 질문 글이 쏟아지는데 파이썬은 최댓값을 제대로 잡았는지, 방문 체크 리스트를 만들어서 이미 방문한 곳인지 아닌지 확인하면 된다. 코드확인 12345678910111213141516171819202122232425from collections import dequedx,dy=[0,0,1,-1],[1,-1,0,0]m,n=map(int,input().split())D=[[*map(int,input().split())] for _ in range(n)]a=[[-1]*m for _ in range(n)]q=deque()for i in r..
-
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) 특수 장비를 사용한 경우, 무조건 인접한 ..