# breadth first search
Minimum Genetic Mutation
오늘은 BFS 관련된 문제를 풀어보기로 했다. 이 문제는 프로그래머스에 나와있는 문제와 굉장히 유사했으며 실제로 Word Ladder 이라는 리트코드 하드문제와 동일한 문제다. 사실 하드 레벨의 난이도라고 하기 조금 민망할정도로 어려운 문제는 아니다. start 와 e
Minimum Jumps to Reach Home
오늘은 개인적으로 꽤 재미난 문제를 풀었다. 굉장히 낮은 acceptance rate 때문에 겁을 먹었지만 일단 들어와서 천천히 풀어봤다. 문제는 x 지점까지 a라는 전진 점프와 b라는 후방 점프가 있을때 가정 적은 점프에 수로 x까지 도달하는 포인트를 리턴해야 하는
Shortest Path with Altering Colors
꽤 새로운 유형의 문제를 풀었다. 그래프나 Matrix에서 탐색하는게 아닌 n이라는 노드가 주어졌을때. 색이 다른 Edge 벡터에 각 노드가 배치되어있는데 Directed Graph 이고 각 노드가 이어질려면은 연결되있는 edge에 색이 달라야한다. 즉, 빨강 색 라인
Nearest Exit from Entrance in Maze
리트코드 그래프 문제 추천리스트에 있었던 미로에서 가장 가까운 탈출구로 도망가야 하는 문제다. BFS유형의 문제는 내가 볼때 두가지의 패턴으로 나뉜다. 하나는 일반적인 Queue 자료구조를 이용한 가능한 모든 경우의 수 찾기, 그리고 Priority_Queue 를 이용
Path With Minimum Effort
BFS 문제를 어떤것들 풀까 하고 보던중에 발견한 문제이다. 언뜻보기에는 간단한 문제지만, 난 어느부분에서 막혔었고 배운점들도 있었기에 적어본다. 문제 내용은 되게 간단하다. 사각형 밑에 가장자리에 도달하기까지 숫자들을 지나게 될텐데 이 경로상에 절대값중에 마지막 숫자
Coin Change
오랜만에 사회에서 풀어보는 문제이다. 확실히 코딩 문제 푸는 기간을 오래 쉬었던만큼 부족한 부분이 많이 느껴졌고. 어떤 문제를 올릴까 고민을 많이 했는데 이 문제가 되게 좋은 문제라는걸 느껴서 올리고싶었다. 예전에 한참 고민을 많이 했었던 2022 SK ICT Fami
리틀 프렌즈 사천성
오랜만에 풀어보는 BFS 문제이다. 사실 요즘 코딩알고리즘을 푸는데 있어서 심한 슬럼프가 온거같은 기분이다. 문제를 읽어도 읽은 기분이 안들고 구현하는데 있어서 조금이라도 어려움이 있게 되면 금방 포기하고 답부터 찾을려는 내 모습이 한심하게 느껴지고 그랬지만 앞으로 문
[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
백준 13549, 숨바꼭질 3 - 다익스트라 / BFS
https://www.acmicpc.net/problem/13549목표 지점을 찾으면 탐색을 종료하는, 일반적인 DFS, BFS는 간선의 가중치가 모두 같아야 함.하지만, 본 문제는 +1, -1 로 가는 경우 가중치가 1,x2 로 가는 경우 가중치가 0 으로
백준 2638, 치즈 - DFS / BFS, 구현, 시뮬레이션
https://www.acmicpc.net/problem/2638맵의 지점이 외부 공기인지, 내부 공기인지를 구분해야 함"모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다."=> 확정된 외부 공기인 map\[0]\[0] 부터 탐색 시작 (DFS /
백준 1600, 말이 되고픈 원숭이 - BFS
https://www.acmicpc.net/problem/1600최단 거리 / 최소 동작 => BFS말 처럼 동작한 횟수에 따라 탐색 경로 구분 1) boolean\[]\[]\[] check: 해당 지점 좌표, 말 처럼 동작한 횟수로 구분 2) Queu
백준 2206, 벽 부수고 이동하기 - BFS
https://www.acmicpc.net/problem/2206최단 거리 => BFS벽을 부수지 않고 이동하는 경우, 벽을 부수고 이동하는 경우의 2가지 경우가 존재=> 방문 확인 배열을 통해 2가지 경우를 구분하여, 서로 다른 경로 간에 간섭하지 못하도록
백준 1068, 트리 - Tree, DFS / BFS
https://www.acmicpc.net/problem/1068인접 리스트에 노드들 입력기존 트리의 Leaf 노드 개수를 구함DFS 로 노드를 삭제해가면서, Leaf 노드가 삭제되면기존 Leaf 노드 개수에서 빼줌예외 처리1) 삭제 노드가 루트 노드인 경우
백준 11725, 트리의 부모 찾기 - Tree, DFS / BFS
https://www.acmicpc.net/problem/11725Tree를 직접 구현 X트리의 자식 노드 개수에 제한이 없음(이진 트리처럼 Left Child, Right Child 형식 X)노드의 연결 정보가 부모 - 자식 순서로 정해져서 입력되지 않음=>
백준 14502, 연구소 - Brute Force, Backtracking, BFS
https://www.acmicpc.net/problem/145021) 추가할 벽 3개 위치 선택 => Backtracking2) 추가할 벽 3개 위치 선택 후, 입력 행렬을 0, 0 ~ n, m 차례로 확인바이러스 칸(2)이고 아직 방문 안한 경우, BFS
백준 12851, 숨바꼭질 2 - BFS
https://www.acmicpc.net/problem/12851BFS 로 최소 시간 갱신해가면서 탐색탐색 종료 조건=> 목표 지점(동생)까지 도달한 최소 시간 < 현재 위치까지 도달한 최소 시간다음 탐색 지점 추가 1) 다음 후보 지점이 범위 안에 있
백준 10026, 적록색약 - DFS / BFS
https://www.acmicpc.net/problem/10026본 문제는 단순히 탐색하는 영역의 수를 찾는 문제이므로, BFS가 더 쉬움입력 행렬을 0, 0 ~ n, n 차례로 확인=> 아직 방문 안했으면 BFS 탐색 시작=> Queue에 탐색 시작 좌표
백준 2468, 안전 영역 - Brute Force, DFS / BFS
https://www.acmicpc.net/problem/2468행렬 입력하면서, 최대 지역 높이 저장브루트 포스로 가능한 비의 양 모두 확인=> DFS 반복=> 비의 양: 0 이상 최대 건물 높이 미만(비의 양 == 0 인 경우, 모든 지역이 안전 영역 =>
백준 16953, A → B - BFS
https://www.acmicpc.net/problem/16953BFS => Queue에서 이전 값을 꺼내서 2가지 연산 수행 1) 연산 결과 값 == B 이면, 탐색 성공 2) 연산 결과 값 < B 이면, Queue 에 추가 3) 연산 결과 값 > B