dfs

(C++) 백준 1260번 [DFS와 BFS]

오랜만에 그래프 문제를 풀었다. 그래서 그런지 조금 낯설었지만 기본적인 문제라 나름 괜찮았다. 아주 전형적이고 기본적인 DFS, BFS문제라 가볍게 풀어보기 좋은 것 같다. 1. 문제 해결방법 구상 - DFS는 스택을 이용, BFS는 큐를 이용. (DFS에서 굳이 스택을 이용하지 않고 재귀를 이용해도 됨, 근데 한번 스택으로 구현해보았다.) - DFS와 BFS의 관건은 언제 노드 방문 처리를 하고, 컨테이너에서 노드를 pop하는 지를 잘 고민해야함. - DFS에서 스택을 이용해서 구현을 한다면, 더 이상 깊은 depth로 갈 수 없을 때( 더이상 edge가 없는 node에 이르렀을 때)를 어떻게 처리해주느냐가 중요. - 뿐만 아니라 부모 노드로 다시 돌아갔을 때, 갈 수 있는 또 다른 node가 있는 지..

(C++) 백준 2468번 [안전 영역]

안녕하세요 평범한 컴공생입니다! 백준 2468번 문제 [안전 영역] 알고리즘 포스팅을 시작해보겠습니다. BFS 문제라서 풀어보려 했던 것이었는데 DFS로 해결을 했습니다. 아직 자료구조들의 명확한 차이와 정확한 이해는 쉽지 않은 것 같습니다. 1. 문제 해결 방법 구상하기 - 비의 높이는 아예 비가 안오는 경우부터 비로 인해 모든 영역이 다 잠기는 경우까지 사이에 있는 값들이 될 수 있습니다. - 그 경우들을 하나 하나 해보면서 가장 안전한 영역이 많을 때를 갱신해줍니다. - height 이차원 배열의 어느 한 지점으로부터 동서남북 네 가지 방향 중 하나를 탐색해주기 위하여 dr, dc의 배열을 선언해줍니다. - 그 다음 탐색 지점이 필드 안의 값이 아니라면(0보다 작거나 N-1 보다 크면) 다음 명령문..

(C++) 백준 14500번 [테트로미노]

안녕하세요 평범한 컴공생입니다. 백준 14500번 [테트로미노] 문제 알고리즘 포스팅을 해보겠습니다.쉽지 않은 문제였지만 그렇다고 도전하기도 전에 겁을 먹을 문제는 아니었습니다. SW역량테스트 문제입니다. 도전해 볼 가치가 있습니다. 1. 문제 해결 방법 구상하기 - 4개의 블럭으로 이어진 조각이다? --> 하나의 시작블럭을 잡고 4개의 블럭을 탐색해가면서 더해주자! - 이전에 탐색을 하였던 블록이거나, 주어진 격자의 범위를 넘어서는 경우처럼 여러 조건을 걸어주어야 한다. - 이 방법대로 한다면 ㅗ 모양과 같은 경우에는 예외의 경우이므로 따로 함수를 만들어 예외처리를 해주어야한다. 케이스 1~4경우로 만들어 ㅜ, ㅓ, ㅏ, ㅗ 의 CASE를 다 탐색해준다. - DFS 형식으로 깊이(CNT) 값을 주어 탐..