BFS 검색 결과
8 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 9934] 완전 이진 트리 (python)

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net BFS를 통해 해결하자! 배열의 중간값이 루트이고 루트를 기준으로 왼쪽 서브루트와 오른쪽 서브루트로 나눌 수 있다. makeTree함수를 통해 서브트리와 현재 깊이를 전달한다. import sys input = sys.stdin.readline K = int(input()) _input = list(map(int, input().split())) tree = [[] for _ in range(K)] def makeTree(arr, x):..

2021. 5. 31. 02:59
개발/알고리즘

[백준 16174] 점프왕 쩰리 (Large) (python)

16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net BFS를 이용하여 풀면 된다. 아래 오른쪽만 가능하다는 점! 처음에 visited 배열을 쓰지 않고 했더니 시간초과가 났다. queue에 시작점을 담는다. arr[x][y] 가 0이라면 더이상 움직일 수 없으므로 break arr[x][y] 가 -1이라면 도착이므로 break import sys from collections import deque input = sys.stdin.readline dx = [0, 1] dy = [1, 0] N = int(input())..

2021. 5. 25. 17:08
카테고리 없음

[백준 1325] 효율적인 해킹 (python)

_max: _max = result answer = [i] elif result == _max: answer.append(i) print(*answer)

2021. 5. 12. 16:16
개발/알고리즘

[백준 3055] 탈출 (python)

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS를 이용하자! 물을 먼저 BFS를 통해 퍼지게 하여 퍼지는 시간을 저장해 고슴도치를 이동하자 arr에 비버의 굴(D)는 sys.maxsize로 update한다. 고슴도치는 이동하므로 고슴도치(S)의 위치를 start에 저장하고 비어있는 곳(.)으로 바꾸어준다. 물은 차는 시간으로 바꾸어 주기 위해 시작은 0으로 바꾸어준다. X는 돌이므로 고슴도치가 방문하지 못하게 visited 배열을 True로 바꾸어준다. 물을 퍼지게 하는 BFS를 한다. 비어있는 곳(.) 에만 퍼지..

2021. 4. 22. 17:47
개발/알고리즘

[백준 16234] 인구 이동 (python)

16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net BFS를 이용하여 인접한 칸과의 차이가 L이상 R이하인지 확인하자! 시간초과가 나서 PyPy3으로 제출하였다. 방문여부를 확인하는 visited배열을 생성한다. arr[i][j]를 돌면서 인구 이동을 할 칸들을 저장할 trans배열을 생성한다. 4방향으로 차이가 L이상 R이하 인것이 있다면 queue와 trans배열에 저장하고 방문 체크, flag, _sum을 update한다. 인구이동이 일어난다면(trans > 1) 각 칸을 _sum // len(..

2021. 4. 20. 23:23
개발/알고리즘

[백준 4485] 녹색 옷 입은 애가 젤다지? (python)

4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net BFS를 이용한다 맵의 정보를 받는 arr배열을 생성한다. 잃은 루피를 저장하는 arr1배열을 생성한다. 방문 여부를 확인하는 visited 배열을 생성한다. queue에는 [잃은 루피수, x좌표, y좌표]를 넣어준다. 상하좌우 이동하며 맵에 해당하는 좌표를 queue에 넣어준다. 마지막 값을 출력한다. import sys import heapq input = sys.stdin.readline dx = [0, 0, -1, 1] dy = [-1,..

2021. 4. 19. 20:33