악곱 == 악성곱슬

음료수 얼려먹기

---

DFS문제로 매우 자주 출제되는 유형

2차원 배열 형태의 구역을 주고 해당 구역을 나누거나 구역의 개수를 세거나 하는 유형

import sys

def dfs(x, y):
    # 인덱스를 벗어 났으면 (배열 인덱스 주의)
    if x < 0 or y < 0 or x >= N or y >= M:
        return False
    # 현재 노드는 방문으로 표시
    if graph[x][y] == 0:
        graph[x][y] = 1
        # 상하좌우 모두 각각 재귀
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

N, M = map(int, sys.stdin.readline().split())
graph = list()
for i in range(N):
    # readline 사용 시 rstrip 을 사용하여 \n을 제거한다
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

# 탐색 시작
answer = 0

for i in range(N):
    for j in range(M):
        if dfs(i, j) is True:
            answer += 1
print(answer)

미로 탈출

---

BFS는 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 따라서 해당 문제는 BFS를 적용하면 유리하다.

import sys
from collections import deque

# 방향을 골라서 움직여야 할 때 리스트형태로 사용
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    # queue 가 비어있을 때까지
    while queue:
        x, y = queue.popleft()
        # 상하좌우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 인덱스 범위 밖이라면
            if nx < 0 or ny < 0 or nx >= N or ny >= M:
                continue
            # 괴물이 있거나 방문 이력이 있거나
            if graph[nx][ny] == 0 or graph[nx][ny] > 1:
                continue
            # 갈 수 있는 길이라면
            queue.append((nx, ny))   # 큐에 삽입
            graph[nx][ny] = graph[x][y] + 1
    return graph[-1][-1]

N, M = map(int, sys.stdin.readline().split())
graph = list()
for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))
print(bfs(0, 0))