# breadth first search

37개의 포스트
post-thumbnail

Minimum Genetic Mutation

오늘은 BFS 관련된 문제를 풀어보기로 했다. 이 문제는 프로그래머스에 나와있는 문제와 굉장히 유사했으며 실제로 Word Ladder 이라는 리트코드 하드문제와 동일한 문제다. 사실 하드 레벨의 난이도라고 하기 조금 민망할정도로 어려운 문제는 아니다. start 와 e

6일 전
·
0개의 댓글
post-thumbnail

Minimum Jumps to Reach Home

오늘은 개인적으로 꽤 재미난 문제를 풀었다. 굉장히 낮은 acceptance rate 때문에 겁을 먹었지만 일단 들어와서 천천히 풀어봤다. 문제는 x 지점까지 a라는 전진 점프와 b라는 후방 점프가 있을때 가정 적은 점프에 수로 x까지 도달하는 포인트를 리턴해야 하는

2022년 5월 14일
·
0개의 댓글
post-thumbnail

Shortest Path with Altering Colors

꽤 새로운 유형의 문제를 풀었다. 그래프나 Matrix에서 탐색하는게 아닌 n이라는 노드가 주어졌을때. 색이 다른 Edge 벡터에 각 노드가 배치되어있는데 Directed Graph 이고 각 노드가 이어질려면은 연결되있는 edge에 색이 달라야한다. 즉, 빨강 색 라인

2022년 5월 13일
·
0개의 댓글
post-thumbnail

Nearest Exit from Entrance in Maze

리트코드 그래프 문제 추천리스트에 있었던 미로에서 가장 가까운 탈출구로 도망가야 하는 문제다. BFS유형의 문제는 내가 볼때 두가지의 패턴으로 나뉜다. 하나는 일반적인 Queue 자료구조를 이용한 가능한 모든 경우의 수 찾기, 그리고 Priority_Queue 를 이용

2022년 5월 6일
·
0개의 댓글
post-thumbnail

Path With Minimum Effort

BFS 문제를 어떤것들 풀까 하고 보던중에 발견한 문제이다. 언뜻보기에는 간단한 문제지만, 난 어느부분에서 막혔었고 배운점들도 있었기에 적어본다. 문제 내용은 되게 간단하다. 사각형 밑에 가장자리에 도달하기까지 숫자들을 지나게 될텐데 이 경로상에 절대값중에 마지막 숫자

2022년 5월 3일
·
0개의 댓글
post-thumbnail

Coin Change

오랜만에 사회에서 풀어보는 문제이다. 확실히 코딩 문제 푸는 기간을 오래 쉬었던만큼 부족한 부분이 많이 느껴졌고. 어떤 문제를 올릴까 고민을 많이 했는데 이 문제가 되게 좋은 문제라는걸 느껴서 올리고싶었다. 예전에 한참 고민을 많이 했었던 2022 SK ICT Fami

2022년 4월 30일
·
0개의 댓글
post-thumbnail

리틀 프렌즈 사천성

오랜만에 풀어보는 BFS 문제이다. 사실 요즘 코딩알고리즘을 푸는데 있어서 심한 슬럼프가 온거같은 기분이다. 문제를 읽어도 읽은 기분이 안들고 구현하는데 있어서 조금이라도 어려움이 있게 되면 금방 포기하고 답부터 찾을려는 내 모습이 한심하게 느껴지고 그랬지만 앞으로 문

2022년 4월 8일
·
0개의 댓글
post-thumbnail

[Leetcode]994. Rotting Oranges

📄 Description You are given an `m x n` grid where each cell can have one of three values: - `0` representing an empty cell, - `1` representing a

2022년 3월 21일
·
0개의 댓글
post-thumbnail

백준 13549, 숨바꼭질 3 - 다익스트라 / BFS

https://www.acmicpc.net/problem/13549목표 지점을 찾으면 탐색을 종료하는, 일반적인 DFS, BFS는 간선의 가중치가 모두 같아야 함.하지만, 본 문제는 +1, -1 로 가는 경우 가중치가 1,x2 로 가는 경우 가중치가 0 으로

2022년 3월 10일
·
0개의 댓글
post-thumbnail

트리(Tree)

기본적인 Tree 구조와 너비 탐색, 깊이 탐색에 대해 알아봅시다!

2022년 2월 28일
·
0개의 댓글
post-thumbnail

백준 2638, 치즈 - DFS / BFS, 구현, 시뮬레이션

https://www.acmicpc.net/problem/2638맵의 지점이 외부 공기인지, 내부 공기인지를 구분해야 함"모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다."=> 확정된 외부 공기인 map\[0]\[0] 부터 탐색 시작 (DFS /

2022년 2월 21일
·
0개의 댓글
post-thumbnail

백준 1600, 말이 되고픈 원숭이 - BFS

https://www.acmicpc.net/problem/1600최단 거리 / 최소 동작 => BFS말 처럼 동작한 횟수에 따라 탐색 경로 구분 1) boolean\[]\[]\[] check: 해당 지점 좌표, 말 처럼 동작한 횟수로 구분 2) Queu

2022년 1월 31일
·
0개의 댓글
post-thumbnail

백준 2206, 벽 부수고 이동하기 - BFS

https://www.acmicpc.net/problem/2206최단 거리 => BFS벽을 부수지 않고 이동하는 경우, 벽을 부수고 이동하는 경우의 2가지 경우가 존재=> 방문 확인 배열을 통해 2가지 경우를 구분하여, 서로 다른 경로 간에 간섭하지 못하도록

2022년 1월 31일
·
0개의 댓글
post-thumbnail

백준 1068, 트리 - Tree, DFS / BFS

https://www.acmicpc.net/problem/1068인접 리스트에 노드들 입력기존 트리의 Leaf 노드 개수를 구함DFS 로 노드를 삭제해가면서, Leaf 노드가 삭제되면기존 Leaf 노드 개수에서 빼줌예외 처리1) 삭제 노드가 루트 노드인 경우

2022년 1월 29일
·
0개의 댓글
post-thumbnail

백준 11725, 트리의 부모 찾기 - Tree, DFS / BFS

https://www.acmicpc.net/problem/11725Tree를 직접 구현 X트리의 자식 노드 개수에 제한이 없음(이진 트리처럼 Left Child, Right Child 형식 X)노드의 연결 정보가 부모 - 자식 순서로 정해져서 입력되지 않음=>

2022년 1월 28일
·
0개의 댓글
post-thumbnail

백준 14502, 연구소 - Brute Force, Backtracking, BFS

https://www.acmicpc.net/problem/145021) 추가할 벽 3개 위치 선택 => Backtracking2) 추가할 벽 3개 위치 선택 후, 입력 행렬을 0, 0 ~ n, m 차례로 확인바이러스 칸(2)이고 아직 방문 안한 경우, BFS

2022년 1월 22일
·
0개의 댓글
post-thumbnail

백준 12851, 숨바꼭질 2 - BFS

https://www.acmicpc.net/problem/12851BFS 로 최소 시간 갱신해가면서 탐색탐색 종료 조건=> 목표 지점(동생)까지 도달한 최소 시간 < 현재 위치까지 도달한 최소 시간다음 탐색 지점 추가 1) 다음 후보 지점이 범위 안에 있

2022년 1월 21일
·
0개의 댓글
post-thumbnail

백준 10026, 적록색약 - DFS / BFS

https://www.acmicpc.net/problem/10026본 문제는 단순히 탐색하는 영역의 수를 찾는 문제이므로, BFS가 더 쉬움입력 행렬을 0, 0 ~ n, n 차례로 확인=> 아직 방문 안했으면 BFS 탐색 시작=> Queue에 탐색 시작 좌표

2022년 1월 20일
·
0개의 댓글
post-thumbnail

백준 2468, 안전 영역 - Brute Force, DFS / BFS

https://www.acmicpc.net/problem/2468행렬 입력하면서, 최대 지역 높이 저장브루트 포스로 가능한 비의 양 모두 확인=> DFS 반복=> 비의 양: 0 이상 최대 건물 높이 미만(비의 양 == 0 인 경우, 모든 지역이 안전 영역 =>

2022년 1월 19일
·
0개의 댓글
post-thumbnail

백준 16953, A → B - BFS

https://www.acmicpc.net/problem/16953BFS => Queue에서 이전 값을 꺼내서 2가지 연산 수행 1) 연산 결과 값 == B 이면, 탐색 성공 2) 연산 결과 값 < B 이면, Queue 에 추가 3) 연산 결과 값 > B

2022년 1월 19일
·
0개의 댓글