🥇 2206번: 벽 부수고 이동하기

• 항해 99에서 자체적으로 새롭게 제작한 크롬 익스텐션 '탭고리즘'이라는 서비스가 최근 공개되었습니다.
• 이 '탭고리즘'에서 출제되는 문제들이 백준 골드나 플레티넘 티어 정도였기 때문에 머리를 깨우는 겸 살짝씩 풀어보고 블로그에 해당 문제들을 리뷰해보고자 합니다!

 

---

👉🏻 2206번: 벽 부수고 이동하기

☀️ 오늘의 문제

from collections import deque

def bfs(n, m, grid):
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[[False] * 2 for _ in range(m)] for _ in range(n)]  # 3차원 방문 배열
    queue = deque([(0, 0, 0, 1)])  # (x, y, 벽 부숨 여부, 거리)
    visited[0][0][0] = True

    while queue:
        x, y, wall_broken, dist = queue.popleft()

        # (N, M)에 도달한 경우
        if ____:
            return dist

        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            if 0 <= nx < n and 0 <= ny < m:  # 유효한 범위인지 확인
                # 벽을 만나지 않은 경우
                if ____:
                    visited[nx][ny][wall_broken] = True
                    queue.append((nx, ny, wall_broken, dist + 1))
                # 벽을 만났지만 아직 부술 수 있는 경우
                elif ____:
                    visited[nx][ny][1] = True
                    queue.append((nx, ny, 1, dist + 1))

    return -1  # 목표 지점에 도달할 수 없는 경우

 

---

🤔 어떻게 풀었을까?

💭 빈칸 1

• 문제에서는 (1, 1)부터 시작해 (N, M)의 위치까지 간다고 나와있지만, 파이썬은 제로부터 시작해야죠. :)
• (1, 1) / (N, M)을 (0, 0) / (N-1, M-1)로 바꿨을 뿐입니다.

# (N, M)에 도달한 경우
if x == N-1 and y == M-1:
    return dist

 

💭 빈칸 2

• 이동 조건을 채우는 문제로, 두 가지 조건만 만족하면 해당 위치로 움직일 수 있습니다.
• grid[nx][ny] == 0은 해당 위치가 벽이 아니기 때문에 이동할 수 있다는 것을 의미하고,
• not visited[nx][ny][wall_broken]는 전에 방문한 적이 없는 위치인지 확인해주는 조건이에요.

# 벽을 만나지 않은 경우
if grid[nx][ny] == 0 and not visited[nx][ny][wall_broken]:
    visited[nx][ny][wall_broken] = True
    queue.append((nx, ny, wall_broken, dist + 1))

 

💭 빈칸 3

• 이미 주석에도 나와있지만, 이번에는 벽을 만났지만 아직 부술 수 있는 경우의 조건을 세우는 문제에요.
• grid[nx][ny] == 1는 현재 이동하려는 위치가 벽인 경우를 말합니다.
• 그리고 wall_broken == 0를 이용해 아직 벽을 부순 적이 없는지도 체크해줘야 합니다. 이 조건이 없으면, 이미 벽을 한 번 부순 상태에서도 다시 벽을 부수는 경우를 허용하게 되는데, 문제에서는 벽을 최대 1번만 부술 수 있기 때문에 제한해줘야 합니다.
• 그래서 not visited[nx][ny][1]로 추가 조건을 걸어 벽을 부순 상태(1)로 해당 위치를 방문하지 않도록 해야합니다.

# 벽을 만났지만 아직 부술 수 있는 경우
elif grid[nx][ny] == 1 and wall_broken == 0 and not visited[nx][ny][1]:
    visited[nx][ny][1] = True
    queue.append((nx, ny, 1, dist + 1))