글 읽기 - (주석有)테케, 반례 전부 맞게 나오는데 시작하자마자 틀리게 나옵니다...

tlaxh000 2년 전 0

테케랑 반례 모두 맞았는데 시작하자마자 틀렸다고 해서 자세한 설명과 함꼐 질문을 드리고자 합니다.

주석을 모두 달았지만 상어가 이동하는 데 쓰이는 Up Down Right Left 에 관한 설명이 주석으로는 부족한 것 같아 추가로 설명드립니다.

Up & Down 의 경우 (R-1) * 2 만큼 cycle을 갖게 됩니다.

아래의 예시를 통해 보면 Down, R = 8 이라고 가정하겠습니다.

Index는 이동한 거리라고 한다면 location은 이동 후 해당 위치가 됩니다.

Down의 경우 시작위치를 1로 설정하고 index=1 이라면 한 칸 내려가 value는 2가 됩니다. 이런식으로 진행하다가 index = 7이라면 R 까지 이동했고 그 후는 진행 방향을 반대로 진행합니다.

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Location(Value)	2	3	4	5	6	7	8	7	6	5	4	3	2	1

다시 1로 돌아올 때까지 진행하고 나면 이후는 반복됩니다.

위의 배열을 두 개를 이어 붙여서 사용합니다.

위 배열은 시작 위치가 1로 고정이지만 배열을 두 개 붙여 2 Cycle을 만들게 되면 시작 위치만큼 shift하게 된다면 모든 위치에서의 이동거리에 따른 location 을 사용할 수 있게 됩니다.

Up, Right, Left도 위와 같은 방식으로 구현했습니다.

from collections import defaultdict
"""
global var.
bowl : 상어가 담긴 수조이다.
sharks : 상어 위치에 대한 정보가 담긴 배열
total : 어부가 잡은 상어 총합
fisher : 어부 위치
Up, Down, Right, Left 는 각각 move를 하기 위한 정보가 담긴 배열이다.
ㄴ=> Up & Down의 경우 (R-1) * 2 를 cycle로 반복되는 것을 이용.
ㄴ=> Right & Left도 마찬가지로 (C-1) * 2를 cycle로 반복되는 것을 이용한다.
위의 아이디어를 적용하면 s <= 1000 에서 s를 크게 줄일 수 있다.
"""
## 어부 낚시 시도.
def fisherman(cur_loc):
    ## 현재 위치에서 낚시를 시도한다. 
    for i in range(1,R+1): ## row 한칸 씩 내려가며 탐색
        if bowl[i][cur_loc]: ## 수조에 
            _, _, s_z = bowl[i][cur_loc] ## 잡은 물고기의 크기 저장
            bowl[i][cur_loc] = 0
            sharks.remove((i, cur_loc)) ## 잡은 물고기는 제거한다.
            return s_z ## 잡은 물고기 return
    return 0

## 상어 이동
def shark_move(sharks):
    ## 움직인 상어를 저장해둔다.
    moved_fish = defaultdict(set)
    
    for shark in sharks:
        ori_r,ori_c = shark ## 상어 기존 위치
        s,d,z = bowl[ori_r][ori_c]  ## 상어 정보
        
        ## 방향과 몇칸 움직이는지에 따라 이동할 위치 정보 담은 배열
        direction = []
        if d <= 2: ## Up & Down
            if d == 1: direction = [0] + Up[R+1-ori_r:(R+1-ori_r)+((R-1)*2)]
            elif d ==2: direction = [0] + Down[ori_r:ori_r+(R-1)*2]
            
            ## s ==0 이라면 움직이지 않는다.
            r = ori_r if s == 0 else direction[s]
            c = ori_c
            ## 이동한 칸과 이전 칸의 정보를 통해 d 재정의한다.
            d = 1 if direction[s] - direction[s-1] < 0 else 2
            
            if not moved_fish[(r,c)]:
                ## 탐색한 위치가 저장되어 있지 않다면 움직인 상어 정보 추가한다.
                moved_fish[(r,c)] = [s,d,z]
            else:
                ## 이미 해당 칸에 상어가 있다면 더 큰 상어만 남긴다.
                _,_, previous_size = moved_fish[(r,c)]
                if previous_size < z: ## 새로 도착한 상어가 더 크면 update하고 아니라면 기존의 상어에게 잡아 먹힌다.
                    moved_fish[(r,c)] = [s,d,z]
        
        elif d >=3: ## Right & Left
            if d==3: direction = [0] + Right[ori_c:ori_c+(C-1)*2]
            elif d==4: direction = [0] + Left[C+1-ori_c:(C+1-ori_c)+((C-1)*2)]
            
            r = ori_r
            ## s==0이라면 움직이지 않는다.
            c = ori_c if s==0 else direction[s]
            ## 이동한 칸과 이전 칸의 정보를 통해 d 재정의
            d = 4 if direction[s] - direction[s-1] < 0 else 3
            
            if not moved_fish[(r,c)]:
                moved_fish[(r,c)] = [s,d,z]
            else:
                _,_, previous_size = moved_fish[(r,c)]
                if previous_size < z:
                    moved_fish[(r,c)] = [s,d,z]
                
        ## 이동하기 전 상어의 위치는 0으로 초기화한다.
        bowl[ori_r][ori_c] = 0

    ## 상어의 정보와 수조 정보를 update한다.
    new_sharks = []
    for k, v in moved_fish.items():
        r,c = k
        s,d,z = v
        new_sharks.append(k)
        bowl[k[0]][k[1]] = v
        
    return new_sharks
    


R, C, M = map(int, input().split())
bowl = [[0]*(C+1) for _ in range(R+1)]
sharks = []
fisher = 0
total = 0

## Move 를 위한 배열
"""
시작점을 1 또는 R 또는 C로 지정하여 방향에 따라 인덱스 만큼 이동했을 때 위치를 담는 배열을 만들고
추후 시작점에 따라 shift하며 사용하기 위해 같은 배열을 두배로 만들어준다.
"""
Up = [i for i in range(R-1, 0, -1)]+ [i for i in range(2,R+1)]
Up = [0] + Up*2
Down = [i for i in range(2,R+1)] + [i for i in range(R-1, 0, -1)]
Down = [0] + Down*2
Right = [i for i in range(2,C+1)] + [i for i in range(C-1, 0, -1)]
Right = [0] + Right*2
Left = [i for i in range(C-1, 0, -1)]+ [i for i in range(2,C+1)]
Left = [0] + Left * 2


for _ in range(M):
    r,c,s,d,z = map(int, input().split())
    ## s를 굳이 여러바퀴 돌지 않도록 update해준다.
    if d <=2: s = s%((R-1)*2)
    elif d>=3: s = s%((C-1)*2)
    
    bowl[r][c] = [s,d,z]
    sharks.append((r,c))

while fisher < C:
    fisher += 1
    total += fisherman(fisher)
    sharks = shark_move(sharks)
print(total)

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

문제

문제

출처

ICPC

(주석有)테케, 반례 전부 맞게 나오는데 시작하자마자 틀리게 나옵니다...

tlaxh000 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말