인프런 커뮤니티 질문&답변
작성한 질문수
DFS 방식으로 푼 것이 맞나요?
작성
·
195
0
안녕하세요. 강의 열심히 잘 듣고 있습니다 :) 궁금한 것이 있어서 질문드립니다.
우선 NumberOfIsland_bfs는 깊이우선탐색을 하는 것이 이해가 되는데 이번 문제는 이해가 잘 되지 않습니다.
오히려 BinaryTreeLevelOrder의 문제유형과 비슷해 보이고 굳이 따지자면 BFS유형인것 같아서요 (root노드의 자식 노드들을 전반적으로 탐색하니까)
BinaryTreeLevelOrder와 다른 점이라면 자료구조가 큐가 아니라 스택이라는 것에 차이정도로 밖에 느껴지지 않습니다.
DFS방식이라면 1,2,4,6,5,3식으로 탐색을 해야하는 것이 맞지 않나요?
제 생각에는 오히려 이전 강의에서 재귀함수로 푼것이 DFS방식이라는 생각이 듭니다.
이번 문제 해설이 DFS방식으로 푼 것이 맞는지? 맞다면 어떻게 이해하면 좋을지 알려주시면 감사하겠습니다.
답변 2
0
정말 감사합니다. Root, Left, Right 방식으로 코딩을해주셔서 이해가 빨리되었습니다. 결국에 root rigth left도 예제를 추가하니 방향만다르지 동일한 dfs방식이더군요.ㅎㅎ node.right.rigth같은 꼬리가 추가적으로 없어서 이해가 잘 안되었었나봅니다.
원래 의문이었던 dfs가 맞냐는 질문에도 bfs방식이 아니라 dfs방식인것도 확실히 이해하였습니다. ( node.right.rigth 같은 예제 추가를 통해서)
제가 잘 이해한 것이 맞겠죠? ㅎㅎ
0
안녕하세요~고성빈님
주신 질문 잘 봤습니다.
먼저 bfs/dfs는 NumberOfIsland로 이해하시면 정통으로 이해하신겁니다.
대부분의 문제는 그렇게 푸시면 될것입니다.^^;
이 문제의 경우에는 약간 헷갈릴수 있는데요
먼저, 이 문제는 Depth를 구할려고하는게 목적입니다.
그래서 queue/stack을 이용했는데요
먼저 queue는 BinaryTreeLevelOrder 문제를 이해하신거처럼 하면됩니다.
(한칸씩 이동하면서 queue에 넣고 삭제하면서 count++ 증가시켜서 depth를 찾고요)
여기서부터 stack의 관한 내용인데요
2가지 관점입니다.
1. TreeNode전체를 dfs로 돌린게 아닙니다.
질문주신내용:(DFS방식이라면 1,2,4,6,5,3식으로 탐색을 해야하는 것이 맞지 않나요?)
네 그렇게 1,2,4,6,5,3식이면 Preorder (Root, Left, Right) 순회하게끔 하면됩니다.
left가 스택에 맨위로 오게해야겠죠 아래처럼 코딩하면됩니다.(full source는 맨 아래 첨부합니다.)
2. 이문제는 stack을 이용할때 각 레벨의 관점에서 담은겁니다.
각 depth에서 stack으로 담은 후 빼고 있습니다.
한 depth 들어갈때마다 담은거죠, 그래서 queue랑 다른게 없지 않냐고 하실수 있는데요
(stack으로 담았기 때문에 다른다는거죠)
우리가 보통 bfs는 queue에 담아서 하나 씩 찾아들어가는거
dfs는 stack, 재귀로 꼬리에꼬리를 무는 방식으로 찾아들어가는거로 이해하듯이
각 depth를 stack에 담았기때문에 dfs방식이라고 한것입니다.
3. 추가적인 의문사항 있으면 바로 질문주세요. 감사합니다.
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) {
this.val = x;
}
}
public class Dfs_stack {
public static void main(String[] args) {
Dfs_stack a = new Dfs_stack();
TreeNode node = new TreeNode(1);
node.left = new TreeNode(2);
node.right = new TreeNode(3);
node.left.left = new TreeNode(4);
node.left.right = new TreeNode(5);
node.left.left.left = new TreeNode(6);
System.out.println("val: " + a.dfs(node));
System.out.println("val: " + a.dfsStack(node));
}
public List<Integer> dfsStack(TreeNode root) {
List<Integer> lists = new ArrayList<>();
if (root == null)
return lists;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tree = stack.pop();
if (tree.right != null)
stack.push(tree.right);
if (tree.left != null)
stack.push(tree.left);
lists.add(tree.val);
}
return lists;
}
public int dfs(TreeNode root) {
// 1
if (root == null)
return 0;
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> valueStack = new Stack<>();
stack.push(root);
valueStack.push(1);
int max = 0;
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// System.out.println("node: " + node.val);
int count = valueStack.pop();
max = Math.max(max, count);
if (node.left != null) {
stack.push(node.left);
valueStack.push(1 + count);
}
if (node.right != null) {
stack.push(node.right);
valueStack.push(1 + count);
}
}
return max;
}
}