haejun IT

맥주 마시면서 걸어가기 from collections import deque import sys sys.stdin = open("9205_맥주마시면서걸어가기_input.txt", "r") t = int(sys.stdin.readline()) def bfs(): queue = deque() queue.append((home[0], home[1])) while queue: x, y = queue.popleft() if abs(x - rock_festival[0]) + abs(y - rock_festival[1])

스타트 링크 풀이 [[1697_숨바꼭질]] 문제와 유사하게 풀 수 있습니다. 방문한 층 수를 기억하기 위한 check 배열을 생성합니다. 시작점인 s를 queue에 넣어주고 이를 pop 하면서 queue에 대한 bfs 탐색을 시작합니다. queue에는 현재의 층 수가 저장되어 있기 때문에 이 층 수가 g가 될 때의 값을 찾으면 되고, queue가 모두 종료될 때 까지 답을 찾지 못한 경우 문제에서 요구한 use the stairs를 출력해주면 됩니다. 여기서 주의해야할 점은 처음에 시작한 지점을 먼저 시작했다고 1로 체크를 해주고, 마지막에 출력 시 출력 값에서 -1로 빼주어야 한다는 점입니다. 예를 들어 입력이 10 10 1 0 1로 들어온 경우, 시작지점을 먼저 체크를 하지 않으면 10번 이동한 것으..

백준 1697 숨바꼭질 풀이 탐색을 하며 타겟이 되는 값을 찾는 가장 최솟값을 찾아야하기 때문에 BFS로 접근을 했습니다. 문제에서 입력으로 주어지는 n, k 값의 범위를 지정해주었기 때문에 이를 활용하여 조건을 걸어주었습니다. 다음 레벨로 탐색을 할 때의 시점을 문제를 기준으로는 1초가 지난 것이라고 판단하고 이를 판단하기 위해서 distance 배열을 생성하였습니다. 이 배열은 이 전의 값에서 +1을 수행하게 되며 이 배열의 값으로 몇초가 지난건지 확인할 수 있습니다. from collections import deque import sys sys.stdin = open("1697_숨바꼭질_input.txt", "r") n, k = map(int, sys.stdin.readline().split())..

https://www.acmicpc.net/problem/7569 bfs를 활용하는 문제 개인적으로 높이까지 주어져 3차원 배열을 사용해서 문제를 푸는 것이 까다로웠다. 또한, 마지막에 max 값을 찾아주는 단계에서 기존에 사용하던대로 max(map(max, check)) 와 같이 최대값을 구할 수 있을 것이라 생각하여 max()를 한번 더 씌워줬는데 최댓값이 정확히 안구해지는 경우가 있더라. 이 부분에서 반례를 찾는데 시간이 오래 걸렸고, 결국 탐색을 하며 최대값을 구하도록 변경하여 통과했다. 함수로 구현하지 않으면 파이썬 인터프리터로는 시간 초과가 발생한다. 시간 초과를 피하기 위해서 input() 대신 sys.stdin.readline()을 사용할 것. 적절히 함수로 분배해줄 것 deque()를 사..