# depth first search

50개의 포스트
post-thumbnail

[백준] 전쟁-전투

두번째로 풀어보는 백준문제이다. 일단 당분간은 리트코드 보다는 이렇게 Visual Studio 를 쓰는 IDE 를 사용하면서 푸는 백준 위주의 문제를 풀것이고 블로그를 업데이트 할것이다. 백준에서 나오는 추천 문제는 제목이 어그로가 상당하다고 생각하지만 이번 문제는 그

어제
·
0개의 댓글
post-thumbnail

Longest Increasing Path in a Matrix

리트코드 추천으로 처음 접하게 된 문제이다. 난이도가 Hard 여서 상당히 걱정을 하고 문제를 읽게 됐는데 생각보다 할만해 보였고 Memoization 을 이용한 DP 방식으로 쉽게 풀수있을거라고 생각했다. Matrix가 주어졌을때 각 원소를 탐색하면서 원소가 커지는

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

Number of Operations to Make Network Connected

기본 개념에 충실하게 배우기 위한 기초적인 DFS 문제를 풀어보았다. n만큼의 컴퓨터들이 존재하고 이 네트워크들이 서로 연결이 되있다고 했을때 가장 최소한의 선을 움직여서 모든 네트워크가 연결이 될수있게 하면 되는 문제이다. 혹시라도 그것이 불가능하다면 -1을 리턴.

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

백준 1520, 내리막 길 - DFS, DP, 메모이제이션

https://www.acmicpc.net/problem/1520오답 노트 - 처음 생각한 DFS + DP 풀이 방식dp\[y]\[x]: 시작 지점 \[0]\[0] -> \[y]\[x] 지점으로 내리막 길로 가는 경로 개수=> Bottom-UP 방식dp\[y]

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

[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

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

[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

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

[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

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

Depth First Search(깊이 우선 탐색)

Depth First Search은 Breath First Search와는 다르게 이진트리의 맨 하단까지 내려가서 search를 하는 것을 우선적으로 하는 탐색이다.stack형 구조를 가지고 있다는 것이 특징이다. 하지만 stack을 사용하지 않고도 구현은 가능하다.위

2022년 3월 5일
·
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

Where Will the Ball Fall

군대근황 부터 얘기하자면 요즘 코로나가 너무 심해져서 휴가를 나가느냐 마느냐의 스트레스가 계속 오고있다. 휴..진짜 빨리 제대를 해야하는데 100일이 깨진 순간부터 고비의 고비다 ㅠㅠ최대한 많은 문제를 풀고싶은데도 의욕이 크게 안나는거보면 조금씩 초반에 불타올랐던게 약

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

백준 3584, 가장 가까운 공통 조상 - Tree, DFS, DP, LCA (Lowest Common Ancestor)

https://www.acmicpc.net/problem/3584루트 노드 찾기입력 트리 노드 정보가 "부모 노드 - 자식 노드" 형태로 주어짐트리 노드 정보 입력할 때, 자식 노드들을 방문 처리=> 입력이 끝난 후, 방문되지 않은 노드가 루트 노드1) 모든

2022년 2월 7일
·
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

백준 2668, 숫자 고르기 - DFS

https://www.acmicpc.net/problem/2668선택한 수들의 index, value가 싸이클을 구성하면 두 집합이 같음ex 1) 1 → 3 → 1선택한 수 index 집합: 1, 3선택한 수 value 집합: 3, 1ex 2) 5 → 5선택한

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

백준 9466, 텀 프로젝트 - DFS

https://www.acmicpc.net/problem/9466팀을 구성하든, 구성하지 못하든 마지막 순서의 노드는 순환을 이룸ex 1) 예제 입력 1에서, 2 → 1 → 3 → 3 (2, 1 은 팀을 못이루지만, 3은 혼자 팀을 이룸)ex 2) 예제 입력

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

백준 1987, 알파벳 - DFS, Backtracking

https://www.acmicpc.net/problem/1987시작 지점 0, 0 에서부터 DFS 시작다음 지점의 알파벳을 아직 방문 안한 경우, 탐색 확장탐색 확장하면서 이동 가능한 칸 최대 개수 갱신 (DFS 함수 파라미터로 전달)재귀 종료 조건: 다음

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

백준 1926, 그림 - DFS & BFS

https://www.acmicpc.net/problem/19262중 for문으로 도화지 0 ~ n-1 확인=> 해당 지점이 그림(1, true)이고 아직 방문 안한 경우, 해당 지점을 기준으로 탐색 (DFS / BFS) 수행1) DFS재귀함수해당 지점을 기준

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