[코드트리 조별과제] 5회차(8/12 ~ 8/18)

5주 차는 DFS(Depth-First Search)에 대해 학습하였습니다.

 

평소 그래프 문제는 BFS(Breadth-First Search)로 풀다 보니 막상 DFS로 푸는 방법이 생각나지 않았습니다. 저번주차까지 Backtracking에 대해 학습했으므로 응용 및 복습 겸 진행해 보았습니다.

 

https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

요약하자면 시작점과 끝점이 고정일 때, 시작점을 통해 끝점에 도달할 수 있는지 확인하는 문제입니다.

n, m = map(int, input().split())

grid = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
flag = False

def dfs(y, x):
    global flag
    if y == n - 1 and x == m - 1:
        flag = True
        return
    if 0 <= y < n and 0 <= x < m and not visited[y][x] and grid[y][x] == 1:
        visited[y][x] = True
        dfs(y + 1, x)
        dfs(y, x + 1)
        return

    return

dfs(0, 0)
print(1 if flag else 0)

1. 탐색과정에서 방문했던 곳을 재방문하지 않기 위해 visited 리스트 생성
2. 도착 여부를 판단하기 위한 변수 선언
3. 시작점부터 탐색 시작
   1. 현재 위치가 유효한 탐색 범위이며 방문하지 않았고 뱀이 없는 경우 탐색 가능
   2. 방문 처리
   3. 현재 위치에서 움직일 수 있는 방향으로 이동
   4. 탐색 위치가 목표 지점에 도달했을 때 탐색 종료

https://www.codetree.ai/missions/2/problems/comfort-zone?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

k값이 얼마일 때, 구역의 수가 최대가 되는지 탐색하는 문제입니다.

import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
max_k = max(max(i) for i in grid)
answer = [1, 0]

def dfs(y, x, k):
    if 0 <= y < n and 0 <= x < m and not visited[y][x] and grid[y][x] <= k:
        visited[y][x] = True
        dfs(y - 1, x, k)
        dfs(y + 1, x, k)
        dfs(y, x - 1, k)
        dfs(y, x + 1, k)
        return True
    return False

def dfs2(y, x):
    if 0 <= y < n and 0 <= x < m and not visited[y][x]:
        visited[y][x] = True
        dfs2(y - 1, x)
        dfs2(y + 1, x)
        dfs2(y, x - 1)
        dfs2(y, x + 1)
        return True
    return False

for k in range(1, max_k):
    area = 0
    visited = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            dfs(i, j, k)
    
    for i in range(n):
        for j in range(m):
            if dfs2(i, j):
                area += 1
    
    if answer[1] < area:
        answer[0] = k
        answer[1] = area

print(*answer)

1. 주어진 맵에서 최대 높이(max_k) 탐색
2. k마다 새롭게 탐색
   1. k가 달라질 때마다 이전 탐색은 무의미해지므로 항상 visited 리스트 초기화
   2. 각 시작점마다 탐색하며 잠기지 않은 영역 탐색
      • 유효 범위이며 아직 방문하지 않았고 k이하인 영역들
   3. 잠기지 않은 영역들이 만들어지면 다시 탐색해서 영역의 수 갱신
      • 방문하지 않은 값들은 잠기지 않은 영역이므로 해당 영역들에 대해 탐색
      • 주어진 위치에서 탐색이 끝나면 잠기지 않은 영역의 수 갱신

해당 문제의 경우, 재귀 깊이 제한을 설정하지 않으면 런타임에러가 발생하는 문제입니다.