[SWEA] 1953 : 탈주범 검거 - Python

문제

코멘트

일단 2차원 배열의 맵이 주어지고, 4방 탐색 -> 현재 위치에서 한 시간마다 주변으로 퍼져나간다 -> BFS

방향 하드코딩
-> 무조건 4방 탐색이 가능한 것이 아니라, 터널의 종류에 따라 갈 수 있는 방향이 각기 다르므로 종류마다 갈 수 있는 방향을 미리 하드코딩

1. 현재 위치에서 해당 방향(4방향 탐색 중에)으로 이동 가능한지 확인
2. 가능하면 이동할 다음 위치 계산
3. 이동할 좌표가 내부 좌표 이면서, 아직 방문 전이면서, 현재 좌표와 연결이 되는지 확인

연결이 되는지 확인하는 것이 핵심 !!
다음 위치의 터널 타입에 대해, 반대 방향으로 이동이 가능한지 확인했어야 했따!!

예를 들어, 현재 위치에서 좌측으로 이동했다면 다음 위치에서는 우측으로 이동이 가능해야 한다.

내 코드

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

# 탈주범이 있을 수 있는 위치의 개수
# 탈주범은 시간당 1의 거리 이동
# 0초가 아닌 1초부터 진행
# 가장 중요한 건, 이동할 좌표가 현재 위치와 파이프가 연결되어야 한다! -> 이 처리가 중요!!

# 각 파이프별로 이동 가능한 방향 처리 -> 리스트로 따로 선언

dx = [-1,0,1,0]
dy = [0,1,0,-1]
types = [
    [0,0,0,0], # 0번 인덱스는 사용 안해
    [1,1,1,1], # 1번 파이프는 모든 방향 이동 가능
    [1,0,1,0], # 2번 파이프는 상 하
    [0,1,0,1], # 3번 파이프는 좌우
    [1,1,0,0], # 4번 파이프는 상 우
    [0,1,1,0], # 5번 파이프는 하 우
    [0,0,1,1], # 6번 파이프는 하 좌
    [1,0,0,1] # 7번 파이프는 상 좌
]

def isInner(x,y):
    if 0<=x<n and 0<=y<m:
        return True
    return False

def BFS(r,c,tp):
    global visited
    dq = deque()
    dq.append((r,c,tp)) # 시작 좌표, 해당 좌표의 파이프
    visited[r][c] = True # 시작점 방문체크 필수 !!!!
    time = 1 # 1초부터 시작
    while dq:
        if time == L:
            break
        size = len(dq)  #매 초마다 현재 들어있던 것들만 돌려야함
        for _ in range(size):
            x,y,type = dq.popleft() # 현재 좌표, 현재 좌표의 파이프 번호
            directions = types[type] # 해당 타입의 리스트 받아와서
            for i in range(4):
                if directions[i] == 1:
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if isInner(nx,ny) and not visited[nx][ny]: # 내부 좌표이면서 아직 방문 전
                        if g[nx][ny] != 0 and types[g[nx][ny]][(i+2) % 4] == 1: # 이동할 좌표가 길이면서, 현재 좌표와 연결 (방향 반대로 연결)
                            visited[nx][ny] = True
                            dq.append((nx,ny,g[nx][ny]))
        time += 1 # 다 끝나면 1초 추가

T = int(input())
for t in range(1,T+1):
    n,m,r,c,L = map(int, input().split()) # 터널 크기, 맨홀 뚜껑 시작 좌표, 탈출 후 소요 시간
    g = [list(map(int, input().split())) for _ in range(n)]

    visited = [[False] * m for _ in range(n)] # 가능한 방향 기록을 위해
    BFS(r,c,g[r][c])
    cnt = 0
    for i in range(n):
        for j in range(m):
            if visited[i][j]:
                cnt += 1

    print(f"#{t} {cnt}")

실수 줄이기

문제를 주어진대로 어떻게 풀어나갈지 잘 생각해보자.
각 파이프 별로 이동 가능한 방향을 따로 리스트로 관리하는 것이 편하겠다는 생각.
초마다 퍼져나가야 하므로 현재까지 큐에 들어있는 애들만 돌려야 한다는 생각.
가장 중요한건 BFS시작할 때 시작점 방문처리 해줬어야 한다!!!
이것 때문에 49/50으로 문제가 안 풀렸다.
또한 핵심은 현재 좌표에서 다음 좌표로 이동할 때 다음 좌표에서는 현재 좌표와는 반대 방향이 연결되어 있어야 했다. 이 체크만 잘 했다면 해결 가능.