Dev_Diary

DFS(Depth First Search) / 깊이 우선 탐색DFS 는 후에 설명될 BFS 와 함께 대표적이고 가장 기초적인 길찾기 알고리즘입니다.깊이 우선 탐색이라는 이름에 걸맞게 우선 깊게 파고들어가고 보는 알고리즘이라고 볼 수 있는데, 일반적으로 복잡하지 않은 길 찾기 문제나 어떤 그래프가 몇 개의 그룹으로 존재하는지 찾는데 많이 사용하곤 합니다. 또 스택(Stack) 이라는 자료구조를 사용하는 것이 특징이며 후입선출이라는 스택의 특징을 잘 이용한 알고리즘입니다. 혹은 재귀 함수로 스택을 사용하지 않고 구현할 수 있지만 후입선출이라는 특징은 여전히 사용됩니다. DFS 를 사용하는 상황에서의 단계를 크게 나누자면 아래와 같습니다. 1. 데이터를 입력2. 데이터에서 그래프 혹은 트리를 생성 ( 특정 노..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 그래프 탐색 문제지만 구현 능력이 조금 필요했습니다. 단순히 이동만 신경쓰는게 아닌 방향이라는 요소가 추가되어 조금 까다롭지만 결국 이 요소만 해결하면 쉽게 해결할 수 있는 문제였습니다. def solution(N, M, r, c, d, data_list): # 움직임 가이드 guide_x = [0, 1, 0, -1, 0, 1, 0, -1, 0] ..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 단순한 그래프 탐색 문제지만 추가 작업이 필요하다. 탐색을 하면서 빙산을 녹여주며 덩어리의 수를 찾는 작업을 반복하면 된다. 탐색 -> BFS 와 녹이는 작업 같이 -> 덩어리 수 카운트 import copy def solution(N, M, field): # 소요 시간 year = 0 while True: # 덩어리 수 cnt = 0 # 방문 기록 visited = [[1 if field[..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 기본적인 그래프 탐색 문제인데 추가 작업이 몇 개 있다. 물의 수위를 바꿔가며 반복적으로 카운팅을 해주면 된다. def solution(N, field): # 최대 지역 수 max_cnt = 0 # 물의 수위 max_water = max([max(row) for row in field]) # 물의 수위를 변경해가며 for water in range(max_water+1): # 지역 수 cnt = 0 # ..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 전형적인 그래프 탐색 문제입니다. 일반적으로 DFS, BFS 중 선택해서 풀면 됩니다. def solution(a, b, n, m, data_list): # 방문기록 visited = [1 for _ in range(n+1)] visited[a] = 0 # 트리 tree = [[] for _ in range(n+1)] for parent, child in data_list: t..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 기본 아이디어는 '무작위로 뽑아서 계산하지 말고 테이블 둘째 줄에 적혀있는 수로 이동하면 적어도 하나의 수는 첫째줄 집합에 포함된다' 입니다. 이런 아이디어를 갖고 어떻게 구현할지 생각해보니 단순히 DFS, 즉 스택을 이용하면 될 것 같다는 생각이 들었습니다. def solution(N, table): # 스택 리스트 stack_list = [] # 자신의 값을 가지면 미리 넣어두기 ..