글 읽기 - 파이썬) 시작하자마자 틀렸습니다

dhdudwn95 2년 전 0

시간/메모리 초과가 뜰줄 알았는데 1%에서 틀렸습니다가 떠서 당황스럽습니다..

게시판 반례는 다 통화한것 같은데.. 왜 시작하자마자 틀린것일까요..?

import sys
from collections import deque

row, col = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().strip()))for _ in range(row)]

def BFS1(x, y):
    global answer
    visited = [[False for _ in range(col)]for _ in range(row)]
    visited[x][y] = True
    q = deque()
    q.append([x, y])

    while q:
        a, b = q.popleft()

        if a == (row-1) and b==(col-1):
            return True

        for dx, dy in [[1,0],[0, 1],[-1, 0],[0,-1]]: # down, right, up
            nx = a + dx
            ny = b + dy
            if 0<=nx<row and 0<=ny<col:
                if not visited[nx][ny] and graph[nx][ny] == 1:
                        answer +=1
                        visited[nx][ny] = True
                        q.append([nx, ny])
                        break
    return False

def BFS2(x, y):
    global answer
    visited = [[False for _ in range(col)]for _ in range(row)]
    visited[x][y] = True
    q = deque()
    q.append([x, y])

    while q:
        a, b = q.popleft()

        if a == (row-1) and b==(col-1):
            return True

        for dx, dy in [[0, 1],[1,0],[-1, 0],[0,-1]]: # right, down, up
            nx = a + dx
            ny = b + dy
            if 0<=nx<row and 0<=ny<col:
                if not visited[nx][ny] and graph[nx][ny] == 1:
                        answer +=1
                        visited[nx][ny] = True
                        q.append([nx, ny])
                        break
    return False
    
min_answer = (row*col)
answer = 1
if BFS1(0,0):
    min_answer = min(answer, min_answer)

answer = 1
if BFS2(0,0):
    min_answer = min(answer, min_answer)
print(min_answer)

ai4youej 2년 전 0

어떤 문제인가요?

dhdudwn95 2년 전 0

헉.. 문제 번호를 안적었네요 ㅎㅎ..

crookid 2년 전 0

input

6 5
11111
00001
11111
11111
10000
11111

output
22

정답은 18입니다.
아마 answer +=1에서 논리적인 오류가 있는 듯 하군요

dhdudwn95 2년 전 0

헉.. 감사합니다.. 이 방식으로는 해결이 안되는 문제였군요.. ! 한 수 배웠습니다ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬) 시작하자마자 틀렸습니다

dhdudwn95 2년 전 0

ai4youej 2년 전 0

dhdudwn95 2년 전 0

crookid 2년 전 0

dhdudwn95 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말