BFS20 [python] 2636. 치즈 문제 출처 2636. 치즈 풀이 주어진 배열에서 가장 외각부터 안쪽으로 한 단계씩 들어가며 모두 없어질 때까지의 시간과 마지막에 남은 치즈의 갯수를 구하는 문제이다. 입력은 가로, 세로 최대 100이며 제한 시간은 1초 이므로 기본적인 BFS 탐색으로도 충분 하다. 치즈가 없어질때 까지의 시간 time과 시간별로 없어지는 치즈의 수인 cnt를 0으로 초기화 한다. 주어진 배열의 상하좌우에 0을 추가해 준다. 치즈가 존재하지 않는 (0, 0) 인덱스를 q에 추가해 준다. q에서 처음꺼를 pop해서 배열의 상하좌우를 탐색하며 아래 조건에 해당하는 인덱스만 q에 추가한다. 배열의 범위(0 = N+2: continue if arr[ny][nx] == 0: arr[ny][nx] = -1 q.append((ny, .. 2019. 7. 4. [python] 7576. 토마토 문제 출처 7576. 토마토 풀이 주어진 배열에서 익은 토마토의 위치를 찾고, 그 위치부터 배열 전체의 가능한 부분을 BFS 탐색 하는 문제이다. 이 문제에서 최악의 경우 배열의 크기는 10^6으로 단순히 리스트 형식의 자료구조로 BFS 탐색을 하게되면 시간초과가 발생한다. 합격 코드는 단순 리스트구조와 heapq, deque로 해결한 풀이를 모두 작성했다. 단순 리스트(시간 초과) M, N = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] q = [] for y in range(N): for x in range(M): if arr[y][x] == 1: q.append((0, y, x)) arr[y][.. 2019. 7. 1. [python] 17086. 아기 상어2 문제 출처 17086. 아기 상어 풀이 상어가 위치한 곳으로부터 가장 먼 곳의 거리를 구하는 문제이다. 특정 포인트로 부터 BFS로 8가지 방향으로 탐색했을때 가장 늦게 상어를 만나는 지점을 구하면 된다. 모든 배열을 탐색하며 상어가 존재하지 않는 빈 칸들의 위치를 배열(vacancies)에 담는다. 최대 안전거리를 구할 변수 max_를 초기화한다. vacancies로 while문을 돌리며 매번 요소 하나를 뽑아 빈 칸으로부터 상어가 존재하는 곳까지의 경로를 담을 큐(q) 배열에 넣는다. 상어가 존재하는 곳까지 BFS 탐색을 할때 방문한 곳을 표시할 배열(check)를 만들어 초기화한다. 탐색을 시작하는 초기 위치정보 q에서 뽑아 d, y, x 변수에 선언한다. 다음 좌표에 해당하는 위치정보를 q에 담을.. 2019. 6. 29. [python] 16236. 아기 상어 문제 출처 16236. 아기 상어 풀이 아기 상어가 물고기를 먹으며 이동하는 최단거리를 구하는 문제이다. 아기 상어는 다음과 같은 조건을 만족하는 경우에만 물고기를 먹을 수 있다. 자신의 크기보다 작거나 같은 물고기가 있는 칸만 지나갈 수 있다. 자신의 크기보다 작은 물고기만 먹을 수 있다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. (거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.) 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 위 조건을 모두 만족하는 최단거리는 우선순위를 고려한 정렬 알고리즘을 통해 구할 수 있다. 하지만 pyt.. 2019. 6. 29. 이전 1 2 3 4 5 다음
