[백준17143/골드1] 낚시왕 - Python

https://www.acmicpc.net/problem/17143

 

매 초마다 기억해야할 것

1. 위치별 상어가 몇마리 들어있는지 (가장 큰 상어가 잡아먹기위해)

2. 각 상어의 속도, 방향, 크기

 

그래서 낚시터 배열 mp 와 상어의 속도, 방향, 크기를 저장할 sharks 딕셔너리를 만들었다.

 

상어 정보 저장

mp = [[[] for _ in range(C)] for _ in range(R)]
sharks = {}
direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]  # 위, 아래, 오른쪽, 왼쪽

for i in range(M):
    r, c, s, d, z = map(int, input().split())  # 위치, 속력, 이동방향, 크기
    heappush(mp[r-1][c-1], (z, i))
    sharks[i] = [s, d-1, z]

 

mp에 상어를 저장할 때는, 같은 위치에 상어가 두 마리 이상 있을 경우 가장 큰상어만 남겨두고 다 없애야 했기 때문에

heap으로 관리하면서 heappop으로 제거하려고 했다.

 

 

그리고 매 초마다 반복할 세가지 함수를 만들었다.

1. 상어 움직이기 함수

2. 같은 위치에 상어가 두마리 이상 있을 경우, 가장 큰 상어가 나머지를 잡아먹는 함수

3. 낚시왕이 상어를 잡는 함수

 

상어 움직이기

def move():
    new_mp = [[[] for _ in range(C)] for _ in range(R)]

    for a in range(R):
        for b in range(C):
        	
            # 해당 위치에 상어 없을 경우 continue
            if not mp[a][b]:
                continue
			
            _, ci = heappop(mp[a][b]) # 상어 크기(샤용안함), 상어 번호
            cs, cd, cz = sharks[ci]   # 해당상어번호(ci)의 속도, 방향, 크기

            na, nb = a, b   # 현재 상어 위치
			
            # 상어 최종 위치 계산
            
            if cd <= 1:  # 위, 아래 방향일 경우
                cycle = (R - 1) * 2   # 상어 이동 가능 범위 (사이클)
                na = (a + cs * direction[cd][0]) % cycle   # 상어 이동
                
                if na >= R:   # 범위 벗어났을 경우 조정
                    na = cycle - na
                    cd = 1 - cd

            else:  # 오른쪽, 왼쪽 방향일 경우
                cycle = (C - 1) * 2   # 상어 이동 가능 범위 (사이클)
                nb = (b + cs * direction[cd][1]) % cycle   # 상어 이동
                
                if nb >= C:   # 범위 벗어났을 경우 조정
                    nb = cycle - nb
                    cd = 5 - cd
			
            # 상어 이동 후, 새로운 위치 저장
            heappush(new_mp[na][nb], (cz, ci))
            sharks[ci] = [cs, cd, cz]

    return new_mp # 새로운 상어 배열 리턴

 

 

같은 위치에 상어가 두 마리 이상 있을 경우, 가장 큰 상어만 남기기

def fight():
    for x in range(R):
        for y in range(C):
        
        	# 해당 위치에 상어가 두마리 이상 있을 경우, 한마리 남을때까지 pop
            while len(mp[x][y]) > 1:
                _, ci = heappop(mp[x][y]) # 해당 위치에서 상어 제거
                sharks.pop(ci)            # 해당 번호의 상어 제거

 

 

낚시왕이 상어 낚시

def fishing(cur): # 낚시왕의 현재 위치 cur

    # 가장 가까운 행 탐색하며 상어 있으면 상어 크기 return
    for r in range(R):
        if mp[r][cur]:
            _, ci = heappop(mp[r][cur])
            size = sharks[ci][2]
            sharks.pop(ci)
            return size
    return 0

 

 

그리고 낚시왕이 열번호 0부터 N-1까지 1초마다 이동하면서 상어 움직이기, 낚시하기 함수를 적용했다.

 

매 초마다 사이클 반복

result = 0

for king in range(C):
    result += fishing(king)
    mp = move()
    fight()

print(result)

 

 

# 성공 코드

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

R, C, M = map(int, input().split())  # 세로, 가로, 상어 수
mp = [[[] for _ in range(C)] for _ in range(R)]
sharks = {}
direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]  # 위, 아래, 오른쪽, 왼쪽

for i in range(M):
    r, c, s, d, z = map(int, input().split())  # 위치, 속력, 이동방향, 크기
    heappush(mp[r-1][c-1], (z, i))
    sharks[i] = [s, d-1, z]


def move():
    new_mp = [[[] for _ in range(C)] for _ in range(R)]

    for a in range(R):
        for b in range(C):

            # 해당 위치에 상어 없을 경우 continue
            if not mp[a][b]:
                continue

            _, ci = heappop(mp[a][b])  # 상어 크기(샤용안함), 상어 번호
            cs, cd, cz = sharks[ci]  # 해당상어번호(ci)의 속도, 방향, 크기

            na, nb = a, b  # 현재 상어 위치

            # 상어 최종 위치 계산

            if cd <= 1:  # 위, 아래 방향일 경우
                cycle = (R - 1) * 2  # 상어 이동 가능 범위 (사이클)
                na = (a + cs * direction[cd][0]) % cycle  # 상어 이동

                if na >= R:  # 범위 벗어났을 경우 조정
                    na = cycle - na
                    cd = 1 - cd

            else:  # 오른쪽, 왼쪽 방향일 경우
                cycle = (C - 1) * 2  # 상어 이동 가능 범위 (사이클)
                nb = (b + cs * direction[cd][1]) % cycle  # 상어 이동

                if nb >= C:  # 범위 벗어났을 경우 조정
                    nb = cycle - nb
                    cd = 5 - cd

            # 상어 이동 후, 새로운 위치 저장
            heappush(new_mp[na][nb], (cz, ci))
            sharks[ci] = [cs, cd, cz]

    return new_mp  # 새로운 상어 배열 리턴


def fight():
    for x in range(R):
        for y in range(C):

            # 해당 위치에 상어가 두마리 이상 있을 경우, 한마리 남을때까지 pop
            while len(mp[x][y]) > 1:
                _, ci = heappop(mp[x][y])  # 해당 위치에서 상어 제거
                sharks.pop(ci)  # 해당 번호의 상어 제거


def fishing(cur): # 낚시왕의 현재 위치 cur

    # 가장 가까운 행 탐색하며 상어 있으면 상어 크기 return
    for r in range(R):
        if mp[r][cur]:
            _, ci = heappop(mp[r][cur])
            size = sharks[ci][2]
            sharks.pop(ci)
            return size
    return 0

result = 0

for king in range(C):
    result += fishing(king)
    mp = move()
    fight()

print(result)

 

 

처음에는 상어 이동을 for문으로 반복하면서 한 칸씩 이동했더니 시간초과났다.

0 <= s (상어 속력) <= 1000인 걸 간과했다.

 

# 실패 코드 (move 함수)

def move():
    new_mp = [[[] for _ in range(C)] for _ in range(R)]

    for a in range(R):
        for b in range(C):
            if not mp[a][b]:
                continue

            _, ci = heappop(mp[a][b])
            cs, cd, cz = sharks[ci]

            na, nb = a, b

            for _ in range(cs):
                tmp_a, tmp_b = na + direction[cd][0], nb + direction[cd][1]

                # 벽에 부딪히면 방향 반전
                if not (0 <= tmp_a < R and 0 <= tmp_b < C):
                    cd = (0 if cd == 1 else 1 if cd == 0 else 2 if cd == 3 else 3)
                    tmp_a, tmp_b = na + direction[cd][0], nb + direction[cd][1]

                na, nb = tmp_a, tmp_b

            heappush(new_mp[na][nb], (cz, ci))
            sharks[ci] = [cs, cd, cz]

    return new_mp