알고리즘

[백준] 2206 - 벽 부수고 이동하기 - 골드 3

swanzzz 2025. 4. 9. 15:45
반응형

[오늘의 문제]

https://www.acmicpc.net/problem/2206

[오늘의 학습 키워드]

  • BFS

1. 문제 설명

 

N x M 행렬의 미로를 탈출하는 문제입니다.

 

0은 이동이 가능한 길

1은 이동이 불가능한 벽을 의미하는데

 

벽은 1번 부술수 있습니다.

 

모든 경로중 가장 짧은 경로를 찾아서 이동 시간을 출력하는 문제입니다.

만약 탈출이 불가능한 경우 -1을 반환합니다.

[제한 사항]

  • 시간 제한 2초
  • 메모리 제한 192MB
  • 1 ≤ N ≤ 1,000
  • 1 ≤ M ≤ 1,000

2. 접근 방식

 

전형적인 BFS 문제 같습니다.

 

벽을 부술수 있을 때 이동 가능한 모든 경로를 queue에 넣어서 다음 위치를 탐색합니다.

 

그 중 벽을 부숴야 하면 부수고 이동한 뒤 그 상태를 queue에 넣어서 종료까지 탐색을 실시합니다.

 

한가지 주의할 점은 이동 시간을 구하는 문제이므로 visited 배열에 이동 시간을 표시하여 visited 배열을 반환하는 방법이 있는데

 

이 문제는 벽을 부수고 이동한 경우와, 벽을 부수지 않고 이동한 경우를 나눠야 하기 때문에 visited 배열을 3차원 배열로 생성해 주어야 합니다.

 

따라서 이동시간을 고려할 count 변수를 따로 생성하고, 3차원 visited 배열을 토대로 이동 가능 여부를 확인하며 count를 반환하면 될 것 같습니다.

 

모든 queue의 탐색이 종료되었는데 반환이 이루어지지 않았다면 이동 불가 판정을 내리고 -1을 반환해주면 될 것 같습니다.

3. 코드

import sys
input = sys.stdin.readline
from collections import deque

# 4방향 탐색
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 정보를 토대로 BFS 탐색 시작
def BFS(sx, sy, ex, ey, wall_break, count):

    # 3차원 방문 배열 생성, 벽을 부수는 경우와 안부순 경우 구분하기 위함
    visited = [[[0] * M for _ in range(N)] for _ in range(2)]

    # 입력받은 wall_break 정보를 토대로 초기 위치 방문 처리
    visited[wall_break][sx][sy] = 1     

    # 모든 정보 queue에 넣기
    queue = deque([(sx, sy, wall_break, count)])    

    while queue:
        x, y, wall_break, count = queue.popleft()

        # 종료 조건 현재 뽑아온 위치가 종료 위치와 동일한 경우 count 반환
        if (x, y) == (ex, ey):
            return count

        # 4방향 탐색 실시
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            # 범위를 벗어나지 않고, 아직 방문하지 않은 곳 찾기
            if 0 <= nx < N and 0 <= ny < M and not visited[wall_break][nx][ny]:
                
                # queue에 이동 정보를 넣는 경우는 2가지만 구분
                # 1. 이동이 가능한 경우
                if maze[nx][ny] == '0':
                    visited[wall_break][nx][ny] = 1
                    queue.append((nx, ny, wall_break, count + 1))
                
                # 2. 벽을 만났는데 부수고 이동이 가능한 경우
                elif maze[nx][ny] == '1' and wall_break:
                    visited[wall_break][nx][ny] = 1
                    queue.append((nx, ny, 0, count + 1))
    
    # queue가 종료되었는데 count를 반환하지 못한 경우는 이동 불가 판정 -> -1 반환
    return -1

# 입력
N, M = map(int, input().split())
maze = [list(input().strip()) for _ in range(N)]    # 빈 칸없고 줄바꿈 문자 포함됨

# BFS 시작위치 와 종료위치
startX, startY = 0, 0
endX, endY = N-1, M-1
print(BFS(startX, startY, endX, endY, 1, 1))

 

[코드 설명]

# 입력
N, M = map(int, input().split())
maze = [list(input().strip()) for _ in range(N)]    # 빈 칸없고 줄바꿈 문자 포함됨

# BFS 시작위치 와 종료위치
startX, startY = 0, 0
endX, endY = N-1, M-1
print(BFS(startX, startY, endX, endY, 1, 1))

 

입력을 받고 BFS 탐색을 실시합니다.

 

입력은 빈 칸이 없고 입력이 종료될 때 줄바꿈이 발생하니 strip으로 제거해 주었고 input으로 바로 입력 받아 주었습니다.

 

BFS의 탐색 위치는 항상 0,0 이고 종료 위치는 N-1, M-1 입니다.

 

가독성을 위해 상단에 정의 후 BFS 탐색을 실시하였습니다.

 

BFS 탐색 결과로 숫자를 반환하니 바로 print를 실시해 주었습니다.

# 4방향 탐색
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 정보를 토대로 BFS 탐색 시작
def BFS(sx, sy, ex, ey, wall_break, count):

    # 3차원 방문 배열 생성, 벽을 부수는 경우와 안부순 경우 구분하기 위함
    visited = [[[0] * M for _ in range(N)] for _ in range(2)]

    # 입력받은 wall_break 정보를 토대로 초기 위치 방문 처리
    visited[wall_break][sx][sy] = 1     

    # 모든 정보 queue에 넣기
    queue = deque([(sx, sy, wall_break, count)])

 

입력받은 정보를 토대로 BFS 함수를 작성해 주었습니다.

 

어차피 BFS는 한 번 탐색할 것이니 visited 배열을 이 안에서 생성해 주었습니다.

 

visited 배열은 벽을 부순경우와 부수지 않은 경우를 구분하기 위해 2개 생성해 주었습니다.

 

또 입력받은 wall_break 정보를 토대로 초기 위치에 방문 처리를 실시하였고 queue에 초기위치, 벽을 부술수 있는 여부, 이동 시간을 넣어 주었습니다.

    while queue:
        x, y, wall_break, count = queue.popleft()

        # 종료 조건 현재 뽑아온 위치가 종료 위치와 동일한 경우 count 반환
        if (x, y) == (ex, ey):
            return count

        # 4방향 탐색 실시
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            # 범위를 벗어나지 않고, 아직 방문하지 않은 곳 찾기
            if 0 <= nx < N and 0 <= ny < M and not visited[wall_break][nx][ny]:
                
                # queue에 이동 정보를 넣는 경우는 2가지만 구분
                # 1. 이동이 가능한 경우
                if maze[nx][ny] == '0':
                    visited[wall_break][nx][ny] = 1
                    queue.append((nx, ny, wall_break, count + 1))
                
                # 2. 벽을 만났는데 부수고 이동이 가능한 경우
                elif maze[nx][ny] == '1' and wall_break:
                    visited[wall_break][nx][ny] = 1
                    queue.append((nx, ny, 0, count + 1))
    
    # queue가 종료되었는데 count를 반환하지 못한 경우는 이동 불가 판정 -> -1 반환
    return -1

 

BFS 탐색을 실시하기 앞서 가장 먼저 종료 조건을 작성해 주었습니다.

 

종료 조건은 현재 위치가 배열의 마지막 행,열에 도착한 경우 이고 그 때 반환할 값은 이동 시간입니다.

 

종료 조건에 만족하지 않는 경우 4방향 탐색을 통해 미로를 탈출하기 시작합니다.

 

탈출의 조건은 0, 0 에서 미로를 벗어나지 않고 길 혹은 벽을 부숴 endX, endY에 도착하는 것입니다.

 

그 조건을 코드로 작성해 보았습니다.

 

미로를 벗어나지 않았고 아직 다음 위치를 방문하지 않은 경우 이동이 가능한 경우를 2가지로 구분해 주었습니다.

 

길을 만나 이동하는 경우, 벽을 부수고 이동하는 경우

 

벽을 부수고 이동하면 wall_break 는 더이상 부술수 없으니 0을 넣어주었고, 이동 횟수는 꾸준히 업데이트 해주었습니다.

 

모든 queue의 탐색이 종료되었는데 종료 조건에 따라 반환되지 않은 경우 이동이 불가능 하니 -1을 반환해 주었습니다.

4. 결과

[회고]

 

이번 문제는 처음 코드를 작성했는데 15% 에서 틀렸습니다

 

반례를 찾아보던 중 다음과 같은 경우를 찾았습니다.

2 4
0111
0010

ans: 5

 

해당 반례의 경우 2차원 배열로 방문 여부를 확인하고 이동한다면 -1이 반환되는 반례 였습니다.

 

저 역시 기존의 코드는 2차원 방문 배열을 사용하였고, 배열 자체에 이전 위치의 이동 정보를 표시하며 업데이트 하였습니다.

 

그 결과 시작위치 1 이후 1,1 위치는 이미 0, 1 에서 벽을 부수고 아래로 내려가는 이동을 실시하여 1, 1 위치에 3이 표시되었습니다.

 

그러니 처음 작성한 방문하지 않은 곳의 탐색 조건을 만족하지 못하고 -1이 반환되는 것이었습니다.

 

이걸 찾고 그 다음에 3차원 방문 배열을 생성하였습니다.

 

처음에는 3차원 방문배열을 만들고 visited[sx][sy][wall_break] 로 표시하였는데, 이렇게 하니 visited[0][0][0] 에 방문 처리를 하지 않고 visited[0][0][1] 위치에 방문 처리를 실시하였습니다.

 

생각해보면 당연한게 벽을 부술수 있는 경우 1값을 넣고 시작했으니 벽을 부술수 있는 1 visited 배열의 0,0 위치를 초기화 해야 하는데 벽을 부술수 없는 0 visited에 0, 1 위치를 초기화 하는 것이었습니다.

 

따라서 벽을 부수는 상태를 먼저 입력하고 visited 초기 위치를 초기화 해주었습니다.

 

그 결과 초기위치를 제대로 초기화 할 수 있었는데, 이렇게 구하려고 하니 방문처리 배열에서 이동 시간을 구하기가 복잡해 졌습니다.

 

따라서 그냥 count 변수를 하나 더 만들었고, count 변수는 벽의 여부와 상관없이 이동 시간이므로 이동할 때 마다 이전 시간 +1 로 계속 업데이트 하였습니다.

 

그 결과 통과되었고 python 에서 가지치기를 어떤걸 할 수 있을 까 고민하였는데, 크게 조건을 더 수정할 수 없었습니다.

따라서 pypy로 한번 동작해보고 마무리 하였습니다.

 

이번 문제는 문제 해결까지 약 40분 정도 걸렸고 반례를 찾지 못했다면 훨씬 시간이 많이 걸렸을 것 같습니다.

반응형