알고리즘/BOJ
-
BOJ 9505 엔터프라이즈호 탈출(Python 3)알고리즘/BOJ 2019. 2. 14. 19:53
https://www.acmicpc.net/problem/9505 일반 BFS로 풀면 python, pypy로는 시간 초과가 나오는 문제이다.그래서 heapq를 이용한 다이젝스트라로 문제를 풀었다. 그동안 다익스트라로 풀어야할 문제를 전부 bfs, deque로 풀어내서(...) heapq를 이용해 직접 풀은 문제는 이번이 처음이다.저번에 숨바꼭질 질문 글을 통해 heapq의 존재를 처음 알게 되었는데 자주 써먹을 수 있을 것 같다. 다이젝스트라는 BFS와 상당히 유사하지만, BFS와의 차이점은 heapq를 이용하기 때문에 q에서 뱉어내는 좌표중에서 가장자리 좌표를 제일 먼저 뱉어내는 값이 최소값이라는 것이다.K는 dict,defaultdict,list 셋중에서 뭘 하든 상관 없어 보인다. 아래 코드는 l..
-
BOJ 13903 출근(Python 3)알고리즘/BOJ 2019. 1. 30. 17:54
https://www.acmicpc.net/problem/13903 푸는 방법은 간단합니다.1. 1행에 있는 C개의 열을 전부 큐에 집어 넣고, BFS를 돌립니다.2. BFS를 다 돌린 후, R행에서 최솟값을 구합니다. 파이썬은 까딱하면 시간 초과가 나오니까 Pypy3으로 제출하는게 좋습니다. 코드확인 1234567891011121314151617181920212223242526from collections import dequen,m=map(int,input().split())D=[list(map(int,input().split())) for _ in range(n)]S=[[-1]*m for _ in range(n)]k=int(input())dx,dy=[0]*k,[0]*kfor i in range(k)..
-
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 코드를 보고 싶으면 거기 들어가서 확인하면 됩..