[codetree] 나이트, 안전지대(BFS, DFS)

나이트(BFS)

| 문제

나이트는 다음과 같이 노란색 위치를 기준으로 검은색 8곳으로 움직임이 가능합니다. n * n 격자 위에서 격자를 벗어나지 않고 나이트가 시작점에서 도착점까지 가는 데 걸리는 최소 이동 횟수를 구하는 프로그램을 작성해보세요.

from collections import deque

n = int(input())
lst = list(map(int, input().split()))
(r1, r2) = (lst[0] - 1, lst[1] - 1)
(r3, r4) = (lst[2] - 1, lst[3] - 1)

visited = [
    [0 for _ in range(n)]
    for _ in range(n)
]

result = [
    [0 for _ in range(n)]
    for _ in range(n)
]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

def can_go(x, y):
    if not in_range(x, y):
        return False
    if visited[x][y] == 1:
        return False    
    return True

dxs, dys = [-2, -1, 1, 2, 2, 1, -1, -2], [1, 2, 2, 1, -1, -2, -2, -1]
q = deque()

def bfs():
    while q:
        x, y = q.popleft()
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if can_go(nx, ny):
                q.append((nx, ny))
                visited[nx][ny] = 1
                result[nx][ny] = result[x][y] + 1
                if nx == r3 and ny == r4:
                    return

###################################################
q.append((r1, r2))
visited[r1][r2] = 1
bfs()

if r1 == r3 and r2 == r4:
    print(0)

elif result[r3][r4] == 0:
    print(-1)
else:
    print(result[r3][r4])

• visited를 사용안했어서 메모리 초과가 났었다. bfs를 사용할 때 visited를 적극 활용하자.

안전지대(DFS)

| 문제

https://www.codetree.ai/missions/2/problems/comfort-zone/description

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

import sys
sys.setrecursionlimit(10**9)

n, m = tuple(map(int, input().split()))
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

visited = [
    [0 for _ in range(m)]
    for _ in range(n)
]


def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

def can_go(x, y, k):
    if not in_range(x, y):
        return False

    if grid[x][y] <= k or visited[x][y] == 1:
        return False
    
    return True

dxs, dys = [1, -1, 0, 0], [0, 0, 1, -1]

def dfs(x, y, k):
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        if can_go(nx, ny, k):
            visited[nx][ny] = 1
            dfs(nx, ny, k)

def make_max():
    max_height = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] > max_height:
                max_height = grid[i][j]
    return max_height


def make_claan():
    for i in range(n):
        for j in range(m):
            visited[i][j] = 0
    

#######################################################
max_height = make_max()

safe_zone = 0
curr_safe_zone = 0
suitable_height = 1

for k in range(1, max_height + 1):
    for i in range(n):
        for j in range(m):
            if can_go(i, j, k):
                #print(i, j, k)
                visited[i][j] = 1
                dfs(i, j, k)
                curr_safe_zone += 1

    if curr_safe_zone > safe_zone:
        safe_zone = max(curr_safe_zone, safe_zone)
        suitable_height = k

    curr_safe_zone = 0
    make_claan()

print(suitable_height, safe_zone)