728x90 깊이우선탐색2 [BOJ/Python] 14503. 로봇 청소기 📌 문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 📌 문제 접근 방법 바보같이 문제 파악을 잘 못해서 어어어어엄청 헤맸다😣 문제를 찬찬히 살펴보자면, 1) 현재 위치를 청소한다. 2) 현재 위치에서 왼쪽 방향부터 차례로 인접한 칸을 탐색한다. 2-1) 청소할 공간이 있다면, 해당 방향(청소할 공간의 방향)으로 회전하여 전진한다. 2-2) 네 방향 모두 청소할 수 없다면, 바라보는 방향(마지막으로 탐색한 방향)을 유지한 채로 후진한다. .. 2021. 10. 13. [Algorithm] DFS, BFS 그래프 탐색 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요 두 가지 방법 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) DFS (깊이우선탐색) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법 마지막에 만났던 갈림길의 정점으로 되돌아가서 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 DFS 알고리즘 시작 정점 v를 결정하여 반문 정점 v에 인접한 정점 중에서 방문하지 않는 정점 .. 2021. 10. 3. 이전 1 다음 728x90