# depth first search
[백준] 전쟁-전투
두번째로 풀어보는 백준문제이다. 일단 당분간은 리트코드 보다는 이렇게 Visual Studio 를 쓰는 IDE 를 사용하면서 푸는 백준 위주의 문제를 풀것이고 블로그를 업데이트 할것이다. 백준에서 나오는 추천 문제는 제목이 어그로가 상당하다고 생각하지만 이번 문제는 그
Longest Increasing Path in a Matrix
리트코드 추천으로 처음 접하게 된 문제이다. 난이도가 Hard 여서 상당히 걱정을 하고 문제를 읽게 됐는데 생각보다 할만해 보였고 Memoization 을 이용한 DP 방식으로 쉽게 풀수있을거라고 생각했다. Matrix가 주어졌을때 각 원소를 탐색하면서 원소가 커지는
Number of Operations to Make Network Connected
기본 개념에 충실하게 배우기 위한 기초적인 DFS 문제를 풀어보았다. n만큼의 컴퓨터들이 존재하고 이 네트워크들이 서로 연결이 되있다고 했을때 가장 최소한의 선을 움직여서 모든 네트워크가 연결이 될수있게 하면 되는 문제이다. 혹시라도 그것이 불가능하다면 -1을 리턴.
백준 1520, 내리막 길 - DFS, DP, 메모이제이션
https://www.acmicpc.net/problem/1520오답 노트 - 처음 생각한 DFS + DP 풀이 방식dp\[y]\[x]: 시작 지점 \[0]\[0] -> \[y]\[x] 지점으로 내리막 길로 가는 경로 개수=> Bottom-UP 방식dp\[y]
[Leetcode]617. Merge Two Binary Trees
You are given two binary trees root1 and root2.Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped wh
[Leetcode] 695. Max Area of Island
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may
[Leetcode]733. 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 s
Depth First Search(깊이 우선 탐색)
Depth First Search은 Breath First Search와는 다르게 이진트리의 맨 하단까지 내려가서 search를 하는 것을 우선적으로 하는 탐색이다.stack형 구조를 가지고 있다는 것이 특징이다. 하지만 stack을 사용하지 않고도 구현은 가능하다.위
백준 2638, 치즈 - DFS / BFS, 구현, 시뮬레이션
https://www.acmicpc.net/problem/2638맵의 지점이 외부 공기인지, 내부 공기인지를 구분해야 함"모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다."=> 확정된 외부 공기인 map\[0]\[0] 부터 탐색 시작 (DFS /
Where Will the Ball Fall
군대근황 부터 얘기하자면 요즘 코로나가 너무 심해져서 휴가를 나가느냐 마느냐의 스트레스가 계속 오고있다. 휴..진짜 빨리 제대를 해야하는데 100일이 깨진 순간부터 고비의 고비다 ㅠㅠ최대한 많은 문제를 풀고싶은데도 의욕이 크게 안나는거보면 조금씩 초반에 불타올랐던게 약
백준 3584, 가장 가까운 공통 조상 - Tree, DFS, DP, LCA (Lowest Common Ancestor)
https://www.acmicpc.net/problem/3584루트 노드 찾기입력 트리 노드 정보가 "부모 노드 - 자식 노드" 형태로 주어짐트리 노드 정보 입력할 때, 자식 노드들을 방문 처리=> 입력이 끝난 후, 방문되지 않은 노드가 루트 노드1) 모든
백준 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)노드의 연결 정보가 부모 - 자식 순서로 정해져서 입력되지 않음=>
백준 2668, 숫자 고르기 - DFS
https://www.acmicpc.net/problem/2668선택한 수들의 index, value가 싸이클을 구성하면 두 집합이 같음ex 1) 1 → 3 → 1선택한 수 index 집합: 1, 3선택한 수 value 집합: 3, 1ex 2) 5 → 5선택한
백준 9466, 텀 프로젝트 - DFS
https://www.acmicpc.net/problem/9466팀을 구성하든, 구성하지 못하든 마지막 순서의 노드는 순환을 이룸ex 1) 예제 입력 1에서, 2 → 1 → 3 → 3 (2, 1 은 팀을 못이루지만, 3은 혼자 팀을 이룸)ex 2) 예제 입력
백준 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 인 경우, 모든 지역이 안전 영역 =>
백준 1987, 알파벳 - DFS, Backtracking
https://www.acmicpc.net/problem/1987시작 지점 0, 0 에서부터 DFS 시작다음 지점의 알파벳을 아직 방문 안한 경우, 탐색 확장탐색 확장하면서 이동 가능한 칸 최대 개수 갱신 (DFS 함수 파라미터로 전달)재귀 종료 조건: 다음
백준 1926, 그림 - DFS & BFS
https://www.acmicpc.net/problem/19262중 for문으로 도화지 0 ~ n-1 확인=> 해당 지점이 그림(1, true)이고 아직 방문 안한 경우, 해당 지점을 기준으로 탐색 (DFS / BFS) 수행1) DFS재귀함수해당 지점을 기준