BFS

🔒 Problem 🔑 BFS approach Create two queue with bread-first search to all nodes. To handle null case, if null, don't add left & right nodes to queue BFS Code (Kotlin) import java.util.LinkedList import java.util.Queue class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null } class SameTree { fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean { // 1. queue 2개 초기화 및..

Breadth First Search

이론 정리한지 1년이 넘어서 풀어보는 예제 🔒 문제 위상 정렬 순서에 맞는 answer vector를 리턴하라. 🔑 풀이 class Solution{ public: vector topoSort(int V, vector adj[]) { int * indegree = new int[V]{0}; std::vector answer; // initialize indegree array for (int i = 0; i < V; i++) { for (const auto& adjacentVertex : adj[i]) { indegree[adjacentVertex]++; } } std::queue queue; // indegree 0 찾고 넣기 for (int i = 0; i < V; i++) { if(indegree[..

문제 문제 이해하기 여타 다른 문제와 입력값이 좀 다른데 다른 문제는 보통 graph matrix를 제시하고 1,0으로 vertex가 존재하는지 존재하지 않는지를 표현한다면 이 문제는 adjacecy matrix를 아예 입력값으로 제시한다. 때문에 다음과 같이 해석했다. (0)번 노드 기준 (1)번 노드 기준 (2)번 노드는 아무런 노드와도 연결되지 않았다. (2번 행 또는 열에서 자기 자신을 제외한 모든 원소 0) (3)번 노드 기준 따라서 위와 같은 4*4 인접 행렬이 주어졌을때 return 값 (그래프 수)는 2가된다. 해결 방법 방문 여부를 keep하는 visited[]행렬 대신 BFS로 방문하며 방문했던 노드의 자리를 0값으로 대치하여 모든 행렬의 원소가 0이될 때까지 BFS의 호출 수를 증가시..

문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해결 방법 행렬에 1로 되어있는 영역 (Graph) 갯수를 구하는 문제 BFS로 풀이한다. 노드간 연결을 수행할 때 양방향으로 해야하는지 단방향으로 해도 되는지 판단한다. 연결 대상 탐색은 우-하방향으로 하고 연결은 양방향 (우-좌, 하-상) 다 수행한다. 구현 [OrganicCabbage.kt] [main.kt]

문제 아이디어 총 단지수 == Graph 갯수 단지 내 집의 수 == Graph 내 노드(Vertex) 수 출력으로 요구하는 값만 봐고 DFS & BFS가 떠올랐다. 총 단지수 => main 에서 DFS 호출 수 단지 내 집의 수 => 한 DFS 내 재귀 호출 수 그래프 연결작업 => 행렬 전체를 돌며 '오른쪽, 아래'로 연결된 [행번호,열번호] 양방향 연결 리스트 추가 약간 헷갈렸던 것이 단지 내 집의 수 (DFS내 재귀 호출 수 카운트) 하는 부분이었다. DFS 코드 // main에서 마지막 argument로 DFS 호출 횟수를 keep하는 변수를 넘겨서 fun dfs (rowIndex: Int, colIndex: Int, callCount: Int) { //start vertex 는 0,0 가정 상..