글 읽기 - 파이썬 고수님들 질문드려요!

omy5123 3년 전 0

답은 맞게 나오는거 같은데,, 시간초과가 납니다.. 생각은 했는데 이미짜고 나서보니,, 건들여보기가 엄두가 안납니다.. 혹시 시간을 줄일방법이 있을까요 ㅠㅠ 너무 막짜놔서 죄송합니다 100 이랑 51은 그냥 50보다 큰수를 넣었습니다.. X 도 돌이라서 0보다 작은 -1을 넣었구요,, 감사합니다!

def bfs(i,j):
    queue = [[i,j]]
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    count = 0
    while queue:
        a, b = queue[0][0], queue[0][1]
        del queue[0]
        for i in range(4):
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < r and 0 <= y < c and arr[x][y] == '.':
                queue.append([x,y])
                arr[x][y] = arr[a][b]+1

def bfs_S(i,j):
    queue = [[i,j]]
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    count = 0
    while queue:
        a, b = queue[0][0], queue[0][1]
        del queue[0]
        for i in range(4):
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < r and 0 <= y < c and arr[x][y] > arr[a][b]:
                queue.append([x,y])
                arr[x][y] = arr[a][b]+1

r, c =map(int, input().split())
q, p =0,0
arr = []
for i in range(r):
    arr.append(list(input()))


for i in range(r):
    for j in range(c):
        if arr[i][j] == '*':
            arr[i][j] = 0
            bfs(i,j)
for i in range(r):
    for j in range(c):
        if arr[i][j] == '.':
            arr[i][j] = 100

for i in range(r):
    for j in range(c):
        if arr[i][j] == 'D':
            arr[i][j] = 51
            q = i
            p = j
for i in range(r):
    for j in range(c):
        if arr[i][j] == 'X':
            arr[i][j] = -1

for i in range(r):
    for j in range(c):
        if arr[i][j] == 'S':
            arr[i][j] = 1
            bfs_S(i,j)

check = True
for i in range(r):
    for j in range(c):
        if arr[i][j] == 51:
            check = False
if check:
    print(arr[q][p]-1)
else:
    print('KAKTUS')

ghghgh777 3년 전 1

BFS에서 리스트를 큐로 사용하지 않으시는 편을 추천드립니다. 자세한 내용은 https://www.acmicpc.net/blog/v...의 Python 섹션을 확인해주세요.

하단의 for-loop도 순서 영향이 없는 것끼리는 묶을 수 있을 것 같네요.

omy5123 3년 전 0

조금 묶어봤는데 이제 틀렸습니다가 뜹니다.. ㅜㅠ 어디가 잘못된걸까요,, 반례가 있을까요

from collections import deque
import sys

input = sys.stdin.readline
def bfs(i,j):
    queue = deque()
    queue.append([i,j])
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < r and 0 <= y < c and arr[x][y] == '.':
                queue.append([x,y])
                arr[x][y] = arr[a][b]+1

def bfs_S(i,j):
    queue = deque()
    queue.append([i,j])
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < r and 0 <= y < c and arr[x][y] > arr[a][b]:
                queue.append([x,y])
                arr[x][y] = arr[a][b]+1

r, c =map(int, input().split())
q, p =0,0
arr = []
for i in range(r):
    arr.append(list(input()))


for i in range(r):
    for j in range(c):
        if arr[i][j] == '*':
            arr[i][j] = 0
            bfs(i,j)
            break

for i in range(r):
    for j in range(c):
        if arr[i][j] == '.':
            arr[i][j] = 52
        elif arr[i][j] == 'D':
            arr[i][j] = 51
            q = i
            p = j
        elif arr[i][j] == 'X':
            arr[i][j] = -1

check = True

for i in range(r):
    for j in range(c):
        if arr[i][j] == 'S':
            arr[i][j] = 1
            bfs_S(i,j)
            if arr[q][p] == 51:
                check = False
                break

if check:
    print(arr[q][p]-1)
else:
    print('KAKTUS')

ghghgh777 3년 전 1

우선 물이 들어오는 날과 해당 위치에 도착하는 최소 날짜를 같은 리스트에 저장하다 보니 조건문에 문제가 발생하지 않나 싶습니다. 이를 분리하시는 편이 좋을 것 같습니다.

다음으로 이 문제의 답은 50을 넘어갈 수 있는데 그 경우 KAKTUS가 출력될 것으로 보입니다.

또한 *이 둘 이상 포함된 경우 하나의 *에 대해 BFS를 돌고 다음 *에 대한 BFS를 돌 때 .들이 이미 덮어써진 상태라 업데이트가 이루어지지 않아 문제가 있을 듯 싶습니다. 예를 들어,

5 5

..*..

.....

D..S.

..*..

같은 경우입니다.

omy5123 3년 전 0

감사합니다 ㅠ 사람들꺼 보면서 이해하고 다시 짜서 해결하였습니다! 리스트도 두개만들고 큐도 두개만들어서 물들어오는거랑 위치를 따로 저장해주었습니다!!

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

문제

문제

출처

ICPC

파이썬 고수님들 질문드려요!

omy5123 3년 전 0

ghghgh777 3년 전 1

omy5123 3년 전 0

ghghgh777 3년 전 1

omy5123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말