BOJ - 낚시왕 17143번 (python)

❓ 문제 - 백준 낚시왕 17143번 - python 풀이법

 

출처 

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

17143번: 낚시왕

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• graph 리스트에 상어의 정보 (크기, 속력, 이동방향)을 입력받아 저장한다.
• 낚시왕이 모든 열을 돌면서 해당 열에서 상어가 1마리 이상 있다면, 가장 가까운 행에 위치한 상어를 잡아먹고 먹은 상어의 크기를 eat_count에 더해준다.
• 낚시왕이 낚시한 후에 moving() 함수를 통해 상어를 움직인다.
• 상어가 움직인 후에 격자판에 상어가 2마리 이상 있을 수도 있으므로 격자판 행,열에 두 마리 이상의 상어가 있다면 상어의 크기를 내림차순으로 정렬한 후 제일 큰 상어를 제외하고 모두 다 제거해준다.

2. moving()

• 이중 for문으로 graph의 리스트만을 가지고 상어의 움직임을 구현하면 중간에 이동한 상어를 다시 이동될 수 있으므로 g라는 r행, c열의 이차원 리스트로 상어가 이동한 후의 위치를 저장한다.
• graph 리스트에 만약 상어가 들어있다면 상어의 속력만큼 상어를 이동시키기 위해 while문으로 구현한다.
• 상어를 해당 방향으로 상어를 이동시키기 위해 nx, ny를 구한 후 이동시킬 위치가 만약 범위를 벗어나면 방향을 바꾸게 해준다.  북 -> 남, 남 -> 북, 동 -> 서, 서- > 동으로 방향을 변경해준다.
• 만약 범위를 벗어나지 않고 한 칸 이동할 수 있으면 해당 위치로 이동시킨 후 이동해야할 갯수를 -1 해준다.
• 만약 이동해야할 갯수가 0인 경우 상어의 이동을 멈추고 해당 상어의 위치에 상어의 크기, 속력,  변경된 방향을 append 해준다.
• 모든 상어의 이동이 끝나면 g에 저장된 상어의 위치와 정보들을 graph 리스트에 저장한다.

 

💻 소스코드

# 낚시왕 - BOJ 17143
# 구현
r, c, m = map(int, input().split())                                                   
# 북 - 남 - 동 - 서                                                                       
dx = [-1, 1, 0, 0]                                                                    
dy = [0, 0, 1, -1]                                                                    
                                                                                      
graph = [[[] for _ in range(c)] for _ in range(r)]                                    
                                                                                      
for _ in range(m):                                                                    
    x, y, s, d, z = map(int, input().split())                                         
    graph[x-1][y-1].append([z, s, d-1])                                               
                                                                                      
def moving():                                                                         
    g = [[[] for _ in range(c)] for _ in range(r)]                                    
    for i in range(r):                                                                
        for j in range(c):                                                            
            if graph[i][j]:                                                           
                x, y = i, j                                                           
                z, s, d = graph[i][j][0]                                              
                s_count = s                                                           
                while s_count > 0:                                                    
                    nx = x + dx[d]                                                    
                    ny = y + dy[d]                                                    
                    if 0 > nx or nx >= r or ny < 0 or ny >= c:                        
                        if d in [0, 2]:                                               
                            d += 1                                                    
                        elif d in [1, 3]:                                             
                            d -= 1                                                    
                        continue                                                      
                    else:                                                             
                        x, y = nx, ny                                                 
                        s_count -= 1                                                  
                g[x][y].append([z, s, d])                                             
    for i in range(r):                                                                
        for j in range(c):                                                            
            graph[i][j] = g[i][j]                                                     
                                                                                      
eat_count = 0                                                                         
                                                                                      
for i in range(c):                                                                    
    for j in range(r):                                                                
        if graph[j][i]:                                                               
            value = graph[j][i][0]                                                    
            eat_count += value[0]                                                     
            graph[j][i].remove(value)                                                 
            break                                                                     
                                                                                      
    moving()                                                                          
                                                                                      
    for p in range(r):                                                                
        for q in range(c):                                                            
            if len(graph[p][q]) >= 2:                                                 
                graph[p][q].sort(reverse=True)                                        
                while len(graph[p][q]) >= 2:                                          
                    graph[p][q].pop()                                                 
                                                                                      
                                                                                      
print(eat_count)