글 읽기 - 18045 경쟁적감염 도움 부탁드려요

lsk4393 3년 전 0

테케는 맞는데.. 왜 틀린지 모르겠습니다. ㅠㅠ

아이디어는 바이러스 위치와 값을 저장하고 우선순위 정렬을 통해서 BFS를 진행하는 방식으로 했습니다.

어디가 문제일까요?

from copy import deepcopy

N , K = map(int, input().split())

arr = [[0 for j in range(N)] for i in range(N)]
virus_p = []
answer = 0

dx = [0,0,-1,1]
dy = [1,-1,0,0]

for i in range(N):
    for j, v in enumerate(map(int,input().split())):
        arr[i][j] = v
        if arr[i][j] != 0 :
            virus_p.append([i,j,arr[i][j]])

S , X , Y = map(int, input().split())

def bfs() :
    global answer
    global virus_p

    while virus_p :
        virus_p.sort(key = lambda x : x[2])
        size = len(virus_p)
        temp = []

        for i in range(size):
            virus = virus_p[0]
            virus_p.pop(0)

            for j in range(0,4) :
                nx = virus[0] + dx[j]
                ny = virus[1] + dy[j]

                if nx < 0 or ny < 0 or nx > N-1 or ny > N-1 :
                    continue
                if arr[nx][ny] != 0 :
                    continue

                arr[nx][ny] = arr[virus[0]][virus[1]]
                temp.append([virus[0],virus[1],arr[virus[0]][virus[1]]])
        virus_p = deepcopy(temp)
        answer += 1
        if answer == S :
            print(arr[X-1][Y-1])
            return exit()

bfs()

exponential_e 3년 전 3

아래 예제에서 아무 값도 출력하지 않습니다.

해당 조건에 만족하는 출력이 발생하지 않는 것으로 보입니다.

'만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.'

lsk4393 3년 전 0

앗 감사합니다. 그 부분을 해결하고 고쳤는데도 불구하고 잘 되지 않네요 ㅠㅠ 다른 문제가 있는거 같은데..

from copy import deepcopy

N , K = map(int, input().split())

arr = [[0 for j in range(N)] for i in range(N)]
virus_p = []
answer = 0

dx = [0,0,-1,1]
dy = [1,-1,0,0]

for i in range(N):
    for j, v in enumerate(map(int,input().split())):
        arr[i][j] = v
        if arr[i][j] != 0 :
            virus_p.append([i,j,arr[i][j]])

S , X , Y = map(int, input().split())

def bfs() :
    global answer
    global virus_p

    while virus_p :
        virus_p.sort(key = lambda x : x[2])
        size = len(virus_p)
        temp = []
        print(virus_p)
        for i in range(size):
            virus = virus_p[0]
            virus_p.pop(0)

            for j in range(0,4) :
                nx = virus[0] + dx[j]
                ny = virus[1] + dy[j]

                if nx < 0 or ny < 0 or nx > N-1 or ny > N-1 :
                    continue
                if arr[nx][ny] != 0 :
                    continue

                arr[nx][ny] = arr[virus[0]][virus[1]]
                temp.append([nx, ny,arr[nx][ny]])
        virus_p = deepcopy(temp)
        answer += 1

        if answer == S :
            print(arr[X-1][Y-1])
            return exit()

if S == 0 :
    print(arr[X-1][Y-1])
else:
    bfs()

exponential_e 3년 전 2

우선 28번째줄에 print 빼고 하신거 맞죠..? 아니라면 빼주시구요.

아래 예제 또한 아무것도 출력 못하고 있습니다.

제가 자바 유저라 전반적인 로직을 제대로 이해하고 있는지는 잘 모르겠습니다만, 다 떠나 현재 아래의 예제가 안도는 이유는

answer == s -> 이것 때문으로 보입니다. 지도가 모두 채워진 시간이 10초라고 가정하고 입력이 13초 때의 (x, y)를 구하라고 나오면, 작성자님의 코드는 아무것도 출력을 하지 못하게 됩니다.

아래의 예제도 4초가 되기 전에 이미 맵이 가득 차구요. 그러한 경우 하단의 조건문을 돌지 않고 종료되어 아무 출력이 되지 않는 것으로 보입니다.

16
7 8 0 6 16
13 0 0 0 12
0 0 1 0 3
0 9 0 0 15
0 5 0 11 0
0 0 10 0 0
5 4

lsk4393 3년 전 1

앗.. 그런 반례가 있었군요...

자세한 설명 너무나 감사드립니다. 덕분에 고칠 수 있었습니다. 감사합니다 ^^

ine 3년 전 1

감사합니다 exponential 님

덕분에 해결할수 있었네요!! 대단한 통찰력이십니다 ㅎㅎ

yoxxin 3년 전 1

exponential 님 감사합니다.

덕분에 저도 풀었네요

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

문제

문제

출처

ICPC

18045 경쟁적감염 도움 부탁드려요

lsk4393 3년 전 0

exponential_e 3년 전 3

lsk4393 3년 전 0

exponential_e 3년 전 2

lsk4393 3년 전 1

ine 3년 전 1

yoxxin 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말