글 읽기 - python3 환경에 대해 시간관련 조정이 안되어있는것같습니다.

gnffk1129 3년 전 0

제가 코드를 잘못 짰는지 꽤 오랜시간 고민했습니다.. 다른 C++ 정답 코드도 찾아봤는데 2의 위치를 찾는건 결국 N*M의 시간을 소비하면서도 제출이 성공한 코드가 대부분이더라구요.

문자열을 int로 바꾸는 과정을 생략하여 문자열을 가지고 풀도록 하기도 해봤고

input() 도 sys.stdin.readline으로 바꿔서 풀기도 해봤는데,

python3/pypy3 로 제출해서 시간초과가 나지 않은 사람이 없더라구요

Python3 에 대한 시간 보정이 필요해보입니다

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

N, M = map(int, input().rstrip().split())
deltas = [(1,0), (-1,0), (0,1), (0,-1)]

island = []
visited = [[False for _ in range(M)] for _ in range (N)]
bird = (0,0)

for y in range(N):
    row = input().rstrip()
    for x in range(M):
        if row[x] == "2":
            bird = (x, y, 0)
    island.append(list(row))

dq = deque([bird])

def isValid(y,x):
    global island, N, M
    if (0 <= y < N) and (0 <= x < M):
        return island[y][x] != "1"
    else:
        return False

def isFood(y,x):
    global island
    return 3 <= int(island[y][x]) <=5

def search():
    while dq:
        x, y, move = dq.popleft()
        visited[y][x] = True

        for dx,dy in deltas:
            newy, newx, new_move = y+dy, x+dx, move+1
            if isValid(newy, newx) and visited[newy][newx] == False:
                
                if isFood(newy, newx):
                    return new_move

                visited[newy][newx] = True
                dq.append((newx, newy, new_move))
    return False

answer = search()

if answer:
    print(f"TAK\n{answer}")
else:
    print("NIE")