[백준 17143번] 파이썬 - 낚시왕

백준 17143_낚시왕

17143번: 낚시왕

시간 제한 1초, 메모리 제한 512MB

# 조건

• 낚시왕이 상어 낚시를 하는 곳은 크기가 R x C 인 격자판으로 나타낼 수 있다.
• 격자판의 각 칸은 (r, c)로 나타낼 수 있다.
  • r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
  • 칸에는 상어가 최대 한 마리 들어있을 수 있다.
  • 상어는 크기와 속도를 가지고 있다.

• 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다.
• 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.
  1. 낚시왕이 오른쪽으로 한 칸 이동한다.
  2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
  3. 상어가 이동한다.
• 상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다.
• 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
• 왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다.
• 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다.
• 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

• 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다.
• 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.
• 낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력

• 첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)
• 둘째 줄부터 M개의 줄에 상어의 정보가 주어진다.
  • 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다.
  • (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다.
  • d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
• 두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

# 접근 방법

• 구현 및 시뮬레이션 문제이다.
• 좌표를 편하게 사용하기 위하여 처음에 0행과 0열을 추가로 삽입해준다.
• 이 문제에서 고려해야 될 3가지를 각각의 함수로 정의해준다.
  1. 상어가 경계를 벗어나면 방향을 반대로 바꿔 속력을 유지한채로 이동하는 것
  2. 땅과 제일 가까운 상어를 잡는 것
  3. 덩치가 가장 큰 상어가 나머지 상어를 잡아 먹는 것
• 상어를 입력받으며 딕셔너리에 기록해준다.
  • 임의의 번호 : (위치, 방향, 속력, 크기) 로 딕셔너리에 저장해준다.
  • 또한, 나중에 상어가 몇 마리 들어있는지 판단하기 위하여 arr에 번호로 저장해준다.
• 낚시왕의 위치를 0으로 시작하며 함수로 정의한 3가지를 for문안에서 돌려준다.
  • 낚시왕의 위치를 for문의 인수 i로 생각하고 실행한다.
• 다음 땅과 제일 가까운 상어는 행의 번호가 가장 작은 것이므로, shark 딕셔너리를 순회하여 준다.
  • 현재 낚시왕과 같은 열에 있는 상어를 (번호, 위치) 로 저장해 준 후 행 기준으로 정렬해준다.
  • 이후 제일 앞에 있는 상어의 위치를 -1, -1로 변경해준다.
  • 결과에 출력을 위하여 해당 상어의 크기를 + 해준다.
• 상어를 이동시켜야 되는데, 이동해야 하는 곳이 격자 바깥인 걸 판별하기 위하여
  • 델타함수를 입력에 맞게 상 하 우 좌 로 구성하여 반대방향으로 이동을 상-우 라면 (현재방향 + 1) 로 전환
  • 하-좌 라면 (현재방향 -1) 로 전환
  • 해당 속력을 cnt로 기준삼고 바라보는 방향으로 진행해준다.
  • 경계를 벗어난다면 델타함수 + 2를 해주고 방향전환
• 1초 동안의 상황을 다 진행 한 뒤 2마리 이상의 상어가 있다면, 가장 덩치가 큰 상어 외에 모두를 제거해준다.

pypy pass, python 시간초과 코드

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

# 현재 열의 상어 찾기  
def find_shark(col):  
    val = []  
    for id, info in shark.items():  
        if info[1] == col:  
            val.append((id, *info))  

    if val:  
        val.sort(key=lambda x:x[1], reverse=True)  
        num, a, b, c, d, size = val.pop()  
        arr[a][b].remove(num)  
        shark[num] = (-1, -1)  
        return size  
    else:  
        return 0  

# 상어 이동시키기  
# 상 하 우 좌  
di, dj = [0, -1, 1, 0, 0], [0, 0, 0, 1, -1]  
def move_shark():  
    for id, info in shark.items():  
        # 이미 제거된 상어가 아니라면 이동  
        if info == (-1, -1):  
            continue  
        else:  
            cnt = info[2]  
            if cnt == 0:  
                ni, nj = info[0], info[1]  
            si, sj, d = info[0], info[1], info[3]  
            # 처음 상어 있는 곳에서 제거위해 기록  
            a, b = info[0], info[1]  
            while cnt:  
                ni, nj = si+di[d], sj+dj[d]  
                if 0<ni<=R and 0<nj<=C:  
                    cnt -= 1  
                    si, sj = ni, nj  
                else:  
                    if d == 1 or d == 3:  
                        d = d+1  
                    else:  
                        d -= 1  
                    shark[id] = (ni, nj, info[2], d, info[4])  
            arr[a][b].remove(id)  
            arr[ni][nj].append(id)  

# 상어가 2마리 이상 있는 곳 체크  
def check_shark():  
    for ri in range(1, R+1):  
        for rj in range(1, C+1):  
            if len(arr[ri][rj]) >= 2:  
                now_val = []  
                for k in arr[ri][rj]:  
                    now_val.append((k, shark[k][-1]))  

                now_val.sort(key=lambda x:x[1], reverse=True)  
                for small in range(1, len(now_val)):  
                    shark[now_val[small][0]] = (-1,-1)  
                arr[ri][rj] = [now_val[0][0]]  



R, C, M = map(int, input().split())  
arr = [[[] for _ in range(C+1)] for _ in range(R+1)]  

shark = {}  
result = 0  
for k in range(M):  
    r, c, s, d, z = map(int, input().split())  
    # 행, 열, 속력, 이동방향, 크기로 기록  
    shark[k] = (r, c, s, d, z)  
    arr[r][c].append(k)   

# 농부의 위치는 0부터 시작이지만 1부터 바로 상황을 돌려주어도 상관없다.    for i in range(1, C+1):  
    v = find_shark(i)  
    result += v  
    move_shark()  
    check_shark()  

print(result)

python pass 코드

• 상어가 이동하는 부분을 1칸씩 전진하는 것이 아닌 식을 세워서 O(1)의 시간으로 줄여주었다.
• 우선, 처음 저장을 해줄 때, S를 중복을 없애주고 저장해주었다.
  • 한 방향으로 최대 행-1 or 열 -1 만큼 이동가능하므로
  • 왕복 최대 이동 횟수는 (R-1) * 2 or (C-1) * 2 이다.
  • 이 때, 새로 구한 s 가 격자를 넘는다면 왕복 최대 이동 횟수에서 s를 빼주고, 방향을 반대로 변경해준다.
• 이후 상어를 순회하는데 새로운 격자를 생성후 이동해준다.
  • 이동해야되는 부분이 격자를 벗어난다면
  • 방향을 변경 해주고, ni 또는 nj를 변경해준다.
  • 또한 이동한 칸에 상어가 있다면, 현재 상어보다 먼저 움직였다는 것이 보장되므로, 크기가 작다면 없애준다.

전체 코드

import sys  
input = sys.stdin.readline  
di = [0,-1,1,0,0] # _,상,하,우,좌  
dj = [0,0,0,1,-1]  

def move_shark():  
    board_new = [[-1]*c for _ in range(r)]  
    for idx in range(m):  
        if shark[idx]:  
            i, j, s, d, z = shark[idx]  
            ni,nj,nd = i+di[d]*s, j+dj[d]*s, d  
            if ni < 0:  
                ni = -ni  
                nd = 3 - nd  
            elif ni >= r:  
                ni = 2 * (r - 1) - ni  
                nd = 3 - nd  
            elif nj < 0:  
                nj = -nj  
                nd = 7 - nd  
            elif nj >= c:  
                nj = 2 * (c - 1) - nj  
                nd = 7 - nd  
            ninj_idx = board_new[ni][nj]  
            if ninj_idx == -1:  
                board_new[ni][nj] = idx  
                shark[idx] = [ni, nj, s, nd, z]  
            elif shark[ninj_idx][-1] < z:  
                board_new[ni][nj] = idx  
                shark[idx] = [ni,nj,s,nd,z]  
                shark[ninj_idx] = []  
            else:  
                shark[idx] = []  
    return board_new  

r,c,m = map(int, input().split())  
shark = []  
board = [[-1]*c for _ in range(r)]  
for idx in range(m):  
    i,j,s,d,z = map(int, input().split())  
    i,j = i-1,j-1  
    if d < 3: # 상하  
        s %= 2 * (r - 1)  
        if s >= r:  
            s = 2 * (r - 1) - s  
            d = 3 - d  
    else: # 좌우  
        s %= 2 * (c - 1)  
        if s >= c:  
            s = 2 * (c - 1) - s  
            d = 7 - d  
    shark.append([i,j,s,d,z])  
    board[i][j] = idx  

ans = 0  
for man in range(c):  

    for i in range(r):  
        if board[i][man] != -1:  
            shark_idx = board[i][man]  
            ans += shark[shark_idx][-1]  
            shark[shark_idx] = []  
            board[i][man] = -1  
            break  
    if man == c-1:  
        break  

    board = move_shark()  

print(ans)