# depth first search
알고리즘
인접 행렬 구현 시, O(V^2)인접 리스트 구현 시, O(V + E)재귀함수 or 스택으로 구현가능한 최대 깊이까지 탐색하는 방식① 장점큐에 탐색할 노드들을 저장하는 BFS에 비해, 메모리 소비가 적음② 단점최적 해의 탐색을 보장하지 못함Worst Case의 경우,
[백준] 단지번호 붙히기
백준 기준 실버1에 해당하는 문제이다. 솔직히 좀 어려운 문제들을 위주로 많이 풀어봐서 그런지 이런 단순한 DFS 류 문제는 너무 쉽게 느껴졌다. 그래도 어쨌든 문제는 푼거기 때문에 기록은 간단하게 남기겠다. 1이 집을 나타내는 숫자를 의미할때 집들만 탐색해서 상하좌우
[백준] 뿌요뿌요
이 블로그를 작성하는 지금 내 심정은 너무 진이 빠진 느낌이다. 골드5 수준에 문제고 뿌요뿌요 게임을 모티브로 만들어진 코딩 테스트 문제이다. 시뮬레이션 타입에 문제인데 DFS 까지 포함된 단순하지만은 않는 문제이다. 게임의 룰은 간단하다, R, G, B, Y, P
[백준] 전쟁-전투
두번째로 풀어보는 백준문제이다. 일단 당분간은 리트코드 보다는 이렇게 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에 탐색 시작 좌표