2206

날짜 : 2023. 09. 17

사용 언어 : python

 

문제

 

 

 

코드

DFS(오답)

import sys

n, m = map(int, sys.stdin.readline().split())  # 행, 열
graph = list()
for _ in range(n):
    graph.append(" ".join(sys.stdin.readline().rstrip()).split())
visited = [[False] * m for _ in range(n)]
visited[0][0] = True
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def dfs(r, c, flag, cnt):
    print(r, c, flag, cnt)
    if (r, c) == (n-1, m-1):
        print(cnt)
        exit(0)
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        if nx not in range(n) or ny not in range(m):
            continue
        if not visited[nx][ny]:  # 방문 안한 경우
            if graph[nx][ny] == '1':
                if flag == 1:
                    visited[nx][ny] = True
                    dfs(nx, ny, 0, cnt+1)
                    visited[nx][ny] = False
            else:  # graph[nx][ny] = 0
                visited[nx][ny] = True
                dfs(nx, ny, flag, cnt+1)
                visited[nx][ny] = False

dfs(0, 0, 1, 0)
print(-1)

 

BFS(오답)

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())  # 행, 열
graph = list()
for _ in range(n):
    graph.append(" ".join(sys.stdin.readline().rstrip()).split())
visited = [[[0, True]] * m for _ in range(n)]
visited[0][0] = [1, True]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs():
    queue = deque()
    queue.append([0, 0, True, 1])
    while queue:
        x, y, flag, cnt = queue.popleft()
        # print(x, y, flag, cnt)
        if (x, y) == (n-1, m-1):
            return cnt
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(n) and ny in range(m):  # 범위 확인
                if visited[nx][ny][0] == 0:  # 방문 x
                    if graph[nx][ny] == '1':  # 벽
                        if flag:  # 뚫고 가능
                            visited[nx][ny] = [cnt+1, False]  # 방문처리
                            queue.append([nx, ny, False, cnt+1])
                    else: # 벽 x -> flag 상관없이 이동 가능
                        visited[nx][ny] = [cnt+1, flag]
                        queue.append([nx, ny, flag, cnt+1])
                else:
                    if not visited[nx][ny][1]:  # 벽 뚫은 횟수 최신화 가능 케이스
                        if graph[nx][ny] == '0' and flag:  # 벽 안뚫고 이동 가능
                            visited[nx][ny] = [cnt+1, True]
                            queue.append([nx, ny, flag, cnt+1])
    return -1

res = bfs()

print(res)

 

정답

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())  # 행, 열
graph = list()
for _ in range(n):
    graph.append(" ".join(sys.stdin.readline().rstrip()).split())
visited = [[[0, True]] * m for _ in range(n)]
visited[0][0] = [1, True]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs():
    queue = deque()
    queue.append([0, 0, True, 1])
    while queue:
        x, y, flag, cnt = queue.popleft()
        # print(x, y, flag, cnt)
        if (x, y) == (n-1, m-1):
            return cnt
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(n) and ny in range(m):  # 범위 확인
                if visited[nx][ny][0] == 0:  # 방문 x
                    if graph[nx][ny] == '1':  # 벽
                        if flag:  # 뚫고 가능
                            visited[nx][ny] = [cnt+1, False]  # 방문처리
                            queue.append([nx, ny, False, cnt+1])
                    else: # 벽 x -> flag 상관없이 이동 가능
                        visited[nx][ny] = [cnt+1, flag]
                        queue.append([nx, ny, flag, cnt+1])
                else:
                    if not visited[nx][ny][1]:  # 벽 뚫은 횟수 최신화 가능 케이스
                        if graph[nx][ny] == '0' and flag:  # 벽 안뚫고 이동 가능
                            visited[nx][ny] = [cnt+1, True]
                            queue.append([nx, ny, flag, cnt+1])
    return -1

res = bfs()

print(res)

 

 

풀이

- BFS로 풀이하되, 벽을 뚫고 이동할 수 있는 케이스를 고려해서 풀이한다.

- 방문처리를 위한 리스트 단순 True/False가 아니라, 벽 뚫기 기회를 사용했는지 여부까지를 기록하는 방식으로 기록해야 하기 때문에, 리스트를 저장하는 방식으로 방문처리 리스트를 만든다.

ex) visited[1][2] = [2, True] -> (1, 2)까지 이동하는데 2칸을 이동했고, 벽뚫기 기회가 남아있는 케이스

- 만약 방문하지 않은 좌표의 경우 이동하는 과정에서 벽을 뚫어야 하는지 여부를 검사한 다음, 벽을 뚫지 않는다면 기존 flag를 저장하는 방식으로 큐에 push하고, 벽을 뚫어야 한다면 flag를 False로 변환한 다음 push한다. (사전에 벽을 뚫지 않았을 경우)

- 다만, 해당 좌표까지 이동하면서 동일한 이동거리지만 벽을 뚫지 않고 갈 수 있는 케이스가 있기 때문에 해당 케이스를 위해 따로 조건문을 만들어 최신화할 수 있도록 만든다.

- 물론 벽을 미리 뚫고라도 도착점에 도달할 수 있을 수 있기 때문에 최소거리를 위해서 도착점 도달했을 때 해당거리를 곧바로 리턴할 수 있도록 만든다.

- 다만 큐가 빈 경우는 전부 탐색했음에도 불구하고 도착점에 도달하지 못했다는 것을 의미하기 때문에 -1를 리턴한다.

 

 

알게된 점

- 일반적인 BFS 문제로 알고있었는데 꽤나 고려해야 할 요소가 많아 고민을 했던 것 같다.

- 벽을 뚫고 가는 케이스, 벽을 뚫지 않고 가는 케이스까지는 생각을 했지만, 동일한 위치에 벽을 뚫는 기회를 남기고 갈 수 있는 케이스로 최신화하는 것은 생각하지 못했던 것 같다.

 

 

참고 사이트

-