[BOJ/백준] 17143 낚시왕

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in sorted(shark_dict[y].keys()):
        if shark_dict[y][x]:
            temp = shark_dict[y][x][2]
            del shark_dict[y][x]
            return temp
    return 0
R,C,M = map(int,input().split())
 
shark_dict = [{} for _ in range(C)]
for _ in range(M):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    shark_dict[y][x] = [dire,speed,size]
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    remain_cnt = 0
    move_shark_dict = [{} for _ in range(C)]
    result += fishing(y)
    for shark_y in range(C):
        for shark_x in shark_dict[shark_y]:
            dire, speed, size = shark_dict[shark_y][shark_x]
            nx = shark_x
            ny = shark_y
            if dire in [0,1]:
                for _ in range(speed):
                    nx += dx[dire]
                    if nx >= R-1 or nx <= 0:
                        dire = reverse[dire]
                        if nx >= R:
                            nx = R - 2
                        elif nx<0:
                            nx = 1
 
            else:
                for _ in range(speed):
                    ny += dy[dire]
                    if ny >= C-1 or ny <= 0:
                        dire = reverse[dire]
                        if ny >=C:
                            ny = C-2
                        elif ny<0:
                            ny = 1
            if move_shark_dict[ny].get(nx):
                if move_shark_dict[ny][nx][2] < size:
                    move_shark_dict[ny][nx] = [dire, speed, size]
            else:
                move_shark_dict[ny][nx] = [dire,speed,size]
                remain_cnt += 1
    if remain_cnt:
        shark_dict = [{} for _ in range(C)]
 
        for y in range(C):
            for x in move_shark_dict[y]:
                shark_dict[y][x] = move_shark_dict[y][x]
    else:
        break
 
print(result)

문제에서 정해준대로 구현과 시뮬레이션을 정직하게 한 방법이다.

 

즉 이동도 한칸 한칸씩 이동을 해서 통과는 했지만 시간은 오래 걸리는 풀이 방법이다.

 

 

import sys
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in sorted(shark_dict[y].keys()):
        if shark_dict[y][x]:
            temp = shark_dict[y][x][2]
            del shark_dict[y][x]
            return temp
    return 0
R,C,M = map(int,input().split())
 
shark_dict = [{} for _ in range(C)]
for _ in range(M):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    shark_dict[y][x] = [dire,speed,size]
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    remain_cnt = 0
    move_shark_dict = [{} for _ in range(C)]
    result += fishing(y)
 
    for shark_y in range(C):
        for shark_x in shark_dict[shark_y]:
            dire, speed, size = shark_dict[shark_y][shark_x]
            nx = shark_x + dx[dire]*speed
            ny = shark_y + dy[dire]*speed
            if dire in [0,1]:
                while not(0<=nx<R):
                    if nx<0:
                        nx = -nx
                        dire = reverse[dire]
                    else:
                        nx = (R-1)-(nx-(R-1))
                        dire = reverse[dire]
            else:
                while not(0<=ny<C):
                    if ny<0:
                        ny = -ny
                        dire = reverse[dire]
                    else:
                        ny = (C-1)-(ny-(C-1))
                        dire = reverse[dire]
 
            if move_shark_dict[ny].get(nx):
                if move_shark_dict[ny][nx][2] < size:
                    move_shark_dict[ny][nx] = [dire, speed, size]
            else:
                move_shark_dict[ny][nx] = [dire,speed,size]
                remain_cnt += 1
    if remain_cnt:
        shark_dict = [{} for _ in range(C)]
 
        for y in range(C):
            for x in move_shark_dict[y]:
                shark_dict[y][x] = move_shark_dict[y][x]
    else:
        break
 
print(result)

두번째 풀이는 방향을 한번에 구하는 것을 통해 시간을 아낄수 있었다. 정확히 말하면 한번은 아니지만, 한칸한칸씩 움직이는 것보다 빠르게 만들었다.

 

 

import sys
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in range(R):
        if pos[x][y]:
            size = sharks[pos[x][y]][4]
            del sharks[pos[x][y]]
            pos[x][y] = 0
            return size
    return 0
R,C,M = map(int,input().split())
 
sharks = {}
 
pos = [[0 for _ in range(C)] for _ in range(R)]
for num in range(1,M+1):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    sharks[num] = (x,y,speed,dire,size)
    pos[x][y] = num
 
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    if len(sharks)==0:
        break
    result += fishing(y)
    next_pos = [[0 for _ in range(C)] for _ in range(R)]
    eaten = []
    for num in sharks:
        shark_x,shark_y,speed,dire,size = sharks[num]
        nx = shark_x + dx[dire]*speed
        ny = shark_y + dy[dire]*speed
        if dire in [0,1]:
            while not(0<=nx<R):
                if nx<0:
                    nx = -nx
                    dire = reverse[dire]
                else:
                    nx = (R-1)-(nx-(R-1))
                    dire = reverse[dire]
        else:
            while not(0<=ny<C):
                if ny<0:
                    ny = -ny
                    dire = reverse[dire]
                else:
                    ny = (C-1)-(ny-(C-1))
                    dire = reverse[dire]
 
 
        if next_pos[nx][ny] != 0:
            prev_shark_num = next_pos[nx][ny]
            if sharks[prev_shark_num][4] < size:
                next_pos[nx][ny] = num
                sharks[num] = (nx,ny,speed,dire,size)
                eaten.append(prev_shark_num)
            else:
                eaten.append(num)
 
        else:
            next_pos[nx][ny] = num
            sharks[num] =  (nx,ny,speed,dire,size)
    for num in eaten:
        del sharks[num]
    pos = [row[:] for row in next_pos]
 
print(result)

이 풀이는 상어의 정보를 저장하는 딕셔너리와 상어의 위치를 알 수 있는 리스트를 통해 관리를 해서 푸는 방식이다.