본문 바로가기

Algorithm/BFS

 (64)
(C++, Python3) - 백준(BOJ) : 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442bfs 문제였습니다.📕 풀이방법📔 입력 및 초기화1. n행 m열 부술 수 있는 벽 k를 입력받습니다. 2. 2차원 map_input에 지도를 입력받습니다.📔 풀이과정bfs함수를 수행하며 다음을 진행합니다. 1. i행 j열에 방문해 부순 벽의 개수 k개를 검사하기 위해 queue를 선언 후 행,열,부순 벽의 개수를 tuple형태로 push해줍니다.* python의 경우 일반적인 배열로 queue처럼 사용하면 pop때마다 O(n)이 소요되므로 deque를 사용해줍니다. 2. i행 j열에 k개의 벽을 부쉈을 때 최단경로 check배열을 3차원으로 선언 후 각 원소를 0으로 저장합니다.  2. 인접 4방향에 대해 loop를 수행하며 다음을..
(C++) - LeetCode (easy) 1030. Matrix Cells in Distance Order https://leetcode.com/problems/matrix-cells-in-distance-order/description/ Matrix Cells in Distance Order - LeetCode Can you solve this real interview question? Matrix Cells in Distance Order - You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter). Return the coordinates leetcode.com bfs 문제였습니다. 📕..
(C++) - LeetCode (easy) 733. Flood Fill https://leetcode.com/problems/flood-fill/description/ Flood Fill - LeetCode Can you solve this real interview question? Flood Fill - An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. You should perform a flood fill leetcode.com graph 탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 4방향을 확인할 일차원 배열 dr..
(C++) - LeetCode (easy) 637. Average of Levels in Binary Tree https://leetcode.com/problems/average-of-levels-in-binary-tree/description/ Average of Levels in Binary Tree - LeetCode Can you solve this real interview question? Average of Levels in Binary Tree - Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted. Examp leetcode.com bfs 로 해결한 문..
(C++) - 백준(BOJ) 2251 : 물통 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net bfs문제였습니다. 📕 풀이방법 📔 입력 및 초기화 각 물통의 용량을 저장할 일차원 배열 a, 방문 여부를 저장할 3차원 배열 ck, 정답을 저장할 vector v를 선언 후 입력받습니다. 📔 풀이과정 A, B, C에 담긴 물의 용량을 각각 x,y,z라고 한다면 물을 붓는 상태는 다음과 같이 6가지가 됩니다. 각 상태에는 또 부었을 때 물이 넘치는 경우와 그렇지 않은 경우, 두..
(C++) - 백준(BOJ) 14248 : 점프 점프 https://www.acmicpc.net/problem/14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net bfs 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 돌 개수 n, 돌당 써져 있는 숫자 stone, 방문 여부를 저장할 ck, 시작 점 s, 정답 ans를 선언한 후 적절히 입력받습니다. 📔 풀이과정 어떤 정점에서 시작해도 방문가능한 모든 돌을 방문할 수 있는 알고리즘 중 하나인 bfs를 수행합니다. 1. 현재 돌의 지점을 x라 하면 다음 방문 가능한 돌은 x-sto..
(C++) - 백준(BOJ) 1726 : 로봇 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net bfs 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 방향 배열 dr, dc, 공장 정보 factory, 특정 구역의 움직임 횟수를 저장할 moved, 구조체 Robot, 시작 점 도착점 start, dest를 선언 후 적절히 입력받습니다. 편의상 방향을 바꿔주는 것이 구현에 편합니다. 동,남,서,북 순으로 index를 +1, -1하기 편하게 일차원 방향 배열의 값들을 배치했습니다. 📔 풀이과정 어느 방향에..
(C++) - 백준(BOJ) 2234 : 성곽 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net bitmasking을 이용한 bfs문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n행 m열 벽의 정보를 저장할 2차원 배열 wall 방문 여부를 확인할 이차원 배열 ck 방의 개수를 저장할 roomCnt 가장 넓은 방의 크기를 저장할 biggestRoomSize 벽 하나를 허물었을 때 구할 수 있는 가장 넓은 방의 크기 biggestRoomSize2를 선언하고 입력받습니다. 📔 풀이과정 구해..

티스토리툴바