글 읽기 - 무한루프 도는거 같은데 어디일까요?

dyddnekt1 3년 전 0

BFS 한 번으로 답을 찾는 코드입니다만 WA도 아니고 TLE가 나옵니다.

어떤 문제일까요

import sys
sys.stdin = open('input.txt', 'r')

import heapq


class Solve:
    def __init__(self, R, C):
        self.R = R
        self.C = C
        self.water = [[0 for _ in range(C)] for _ in range(R)]
        self.new_water = []
        self.swan = []

        for r in range(R):
            temp = sys.stdin.readline()
            for c in range(C):
                if temp[c] == 'X':
                    self.water[r][c] = 0
                else:
                    self.water[r][c] = 1
                    self.new_water.append((r, c))

                    if temp[c] == 'L':
                        self.swan.append((r, c))

    def is_ice(self, r, c):
        try:
            return self.water[r][c] == 0
        except IndexError:
            return False

    def is_water(self, r, c):
        try:
            return self.water[r][c] == 1
        except IndexError:
            return False

    def solve(self):
        dist = [[-1 for _ in range(self.C)] for _ in range(self.R)]
        dist[self.swan[0][0]][self.swan[0][1]] = 0
        queue = [(0, (self.swan[0]))]
        while queue:
            d, (r, c) = heapq.heappop(queue)

            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                new_r = r + dr
                new_c = c + dc
                if self.is_water(new_r, new_c) and dist[new_r][new_c] == -1:
                    dist[new_r][new_c] = d
                    heapq.heappush(queue, (d, (new_r, new_c)))
                if self.is_ice(new_r, new_c) and dist[new_r][new_c] == -1:
                    dist[new_r][new_c] = d + 1
                    heapq.heappush(queue, (d + 1, (new_r, new_c)))

        return (dist[self.swan[1][0]][self.swan[1][1]] + 1) // 2


R, C = map(int, input().split())
ans = Solve(R, C)
print(ans.solve())

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

문제

문제

출처

ICPC

무한루프 도는거 같은데 어디일까요?

dyddnekt1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말