본문 바로가기
반응형

BFS6

[LeetCode] 107. Binary Tree Level Order Traversal II [JAVA(자바)] 문제 👉 1. 문제 (Binary Tree Level Order) 이진 트리의 루트가 주어지면 노드 값의 상향식(bottom-up) 순서 순회를 반환합니다. (i.e., from left to right, level by level from leaf to root) Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]2. 풀이 BFS 를 이용한 풀이 Queue 에서 노드를 순서대로 꺼내 list 에 추가한다. Queue 에 left, right 순서로 자식 노드를 추가한다. Bottom-up 순서로 출력하기 위해 각 층을 나타나내는 list를 ret의 0번 인덱스에 추가한다. 3. 코드 /** * Definition for a binary .. 2021. 11. 24.
[백준] 17142 - 연구소 3 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 17142번: 연구소 3 1. 문제 N*N 크기의 연구소는 빈 칸과 벽 그리고 M개의 활성 바이러스로 이루어져 있다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 어떤 바이러스를 놓았을 때, 바이러스가 퍼지는 최소 시간을 출력한다. 2. 풀이 브루트포스와 BFS를 이용한 문제 풀이 브루트포스를 통해 M개의 바이러스를 선택한다. BFS를 통해 바이러스의 전파 최대 시간을 구한다. 3. 코드 from collections import deque N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] selceted = [.. 2021. 11. 22.
[백준] 17141 - 연구소 2 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 17141번: 연구소 2 1. 문제 N*N 크기의 연구소는 빈 칸과 벽 그리고 M개의 바이러스로 이루어져 있다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 어떤 바이러스를 놓았을 때, 바이러스가 퍼지는 최소 시간을 출력한다. 2. 풀이 브루트포스와 BFS를 이용한 문제 풀이 브루트포스를 통해 M개의 바이러스를 선택한다. BFS를 통해 바이러스의 전파 최대 시간을 구한다. 3. 코드 from collections import deque import sys N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] chk, v.. 2021. 11. 22.
[백준] 16236 - 아기 상어 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 16236번: 아기 상어 1. 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 물고기와 아기 상어는 모두 크기를 가지고 있고, 처음 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한칸씩 이동한다. 아기 상어는 자신 보다 큰 물고기 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어의 이동 결정 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 .. 2021. 11. 22.
[백준] 16235 - 나무 재테크 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 16235번: 나무 재테크 1. 문제 양분의 정보가 들어있는 N*N크기의 땅에 M개의 나무를 심는다. 가장 처음에 양분은 모든 칸에 5만큼 들어있다. 나무는 한 칸을 차지하며, 한 칸에는 여러 나무가 심어져 있을 수도 있다. 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 만약 한 칸에 여러 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 양분이 부족한 나무는 즉시 죽는다. 여름에는 봄에 죽은 나무가 양분이 된다. 죽은 나무의 나이를 2로 나눈 값이 해당 칸에 양분으로 추가된다. (소수점 아래는 버림) 가을에는 나이가 5의 배수인 나무가 인접한 8개의 칸에 나이가 1인 나무를 번식한다. K년이 지난 후 살아남은 나무의 수를.. 2021. 11. 22.
[백준] 13460 - 구슬 탈출 2 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 13460번: 구슬 탈출 2 1. 문제 N*M 크기의 보드에서 기울이는 동작을 통해 파란 구슬은 냅두고 빨간 구슬만 구멍으로 뺀다. '.'은 빈 칸, '#'은 벽, 'O'는 구멍, 'R'은 빨간 구슬, 'B'는 파란 구슬을 의미한다. 기울이는 동작은 동,서,남,북 4방향이다. 모든 보드의 가장자리에는 모두 벽('#')이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다. 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다. 2. 풀이 BFS 를 이용한 문제 풀이 (최소 거리 -> BFS -> 큐) 초기 각 구슬.. 2021. 11. 22.
반응형

티스토리툴바