[코드트리] 싸움땅 - Python

문제 링크

https://www.codetree.ai/training-field/frequent-problems/problems/battle-ground/description?page=1&pageSize=20 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이 

실수한 부분은 진 플레이어가 원래 가지고 있던 방향대로 이동하는 부분에서, 방향을 반대로 바꾼 플레이어는 바꾸기 전 방향으로 이동해 준 것이다. 방향을 바꾼 방향으로 이동해주어야 한다. 

 

1. 한 칸 이동 함수 

def move():
    
    for i in range(1,m+1):
        x,y,d,s = players[i]
        board[x][y] = 0
        nx = x + dx[d]
        ny = y + dy[d]
        nd = d
        # 범위를 벗어나면 반대 방향으로 바꿔준다. 
        if nx < 0 or nx >= n or ny < 0 or ny >= n :
            nd = (d+2) % 4 
            nx = x + dx[nd]
            ny = y + dy[nd]

        # 이동한 위치에 누가 있을 경우 
        if board[nx][ny] :
        	# 해당 위치에 있던 플레이어 정보
            p2 = board[nx][ny]
            x2,y2,d2,s2 = players[p2]
            
            # 원래 있던 플레이어가 이긴 경우 
            if s2 + guns[p2] > s + guns[i]:
            	# 포인트 계산 
                point[p2] += (s2 + guns[p2]) - (s + guns[i])
                # 진 플레이어가 총을 가지고 있다면 자리에 내려둔다 
                if guns[i]:
                    graph[nx][ny].append(guns[i])
                guns[i] = 0
                # 진 플레이어 한 칸 이동 
                back(i,nx,ny,nd,s)
                # 이긴 플레이어 총 갱신 
                get_gun(p2, nx, ny)
            
            # 점수가 같을 경우 
            elif s2 + guns[p2] == s + guns[i] :
                # 원래 있던 플레이어가 이긴 경우 
                if s2 > s :
                	# 진 플레이어가 총을 가지고 있다면 자리에 내려둔다 
                    if guns[i]:
                        graph[nx][ny].append(guns[i])
                    guns[i] = 0
                    # 진 플레이어 한 칸 이동 
                    back(i,x2,y2,nd,s)
                    # 이긴 플레이어 총 갱신 
                    get_gun(p2, nx, ny)
                # 새로 온 플레이어가 이긴 경우
                else :
                	# 진 플레이어가 총을 가지고 있다면 자리에 내려둔다 
                    if guns[p2]:
                        graph[nx][ny].append(guns[p2])
                    guns[p2] = 0 
                    # 진 플레이어 한 칸 이동 
                    back(p2,nx,ny,d2,s2)
                    # 새로 이동한 플레이어 위치 갱신 
                    board[nx][ny] = i 
                    players[i] = [nx,ny,nd,s]
                    # 이긴 플레이어 총 갱신 
                    get_gun(i, nx, ny)
            else : 
            	# 포인트 계산 
                point[i] += (s + guns[i]) - (s2 + guns[p2])
                # 진 플레이어가 총을 가지고 있다면 자리에 내려둔다 
                if guns[p2]:
                    graph[nx][ny].append(guns[p2])
                guns[p2] = 0 
                # 진 플레이어 한 칸 이동 
                back(p2,x2,y2,d2,s2)
                # 새로 이동한 플레이어 위치 갱신 
                board[nx][ny] = i 
                players[i] = [nx,ny,nd,s]
                # 이긴 플레이어 총 갱신 
                get_gun(i, nx, ny)
                
        # 이동한 위치에 누가 없을 경우 
        else :
            # 총이 있으면 가장 센 총을 얻는다 
            if len(graph[nx][ny]):
                if max(graph[nx][ny]) > guns[i]:
                    tmp = max(graph[nx][ny])
                    graph[nx][ny].remove(tmp)
                    # 원래 가지고 있던 총이 있다면 자리에 내려둔다 
                    if guns[i]:
                        graph[nx][ny].append(guns[i])
                    guns[i] = tmp
            # 이동한 플레이어 위치 갱신 
            board[nx][ny] = i 
            players[i] = [nx,ny,nd,s]

2. 진 플레이어 이동 함수 

def back(num, x,y,d,s):
    
    for i in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        
        # 범위 벗어나면 오른쪽으로 회전 
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            d = (d+1) % 4
            continue 
        
        # 다른 플레이어가 있으면 오른쪽으로 회전 
        if board[nx][ny] :
            d = (d+1) % 4
            continue 
        
        board[nx][ny] = num 
        players[num] = [nx,ny,d,s]
        
        # 이동한 위치에 총이 있으면 가장 센 총 얻는다
        if len(graph[nx][ny]) > 0 :
            tmp = max(graph[nx][ny])
            graph[nx][ny].remove(tmp)
            guns[num] = tmp 
        break

3. 이긴 플레이어 총 갱신 함수 

def get_gun(num, x,y):	
	# 해당 위치에 총이 없다면 
    if len(graph[x][y]) == 0 :
        return 
    # 현재 가지고 있는 총이 더 세다면 
    if guns[num] > max(graph[x][y]) :
        return 
    # 가장 센 총으로 교환 
    tmp = max(graph[x][y])
    graph[x][y].remove(tmp)
    if guns[num]:
        graph[x][y].append(guns[num])
    guns[num] = tmp

 

전체 코드는 다음과 같다. 

각 배열 별 역할은 아래와 같다. 

graph : 위치별 총의 공격력을 저장 

guns : index에 해당하는 플레이어가 가지고 있는 총의 공격력 저장 

players : index에 해당하는 플레이어의 현재 위치, 방향, 초기 공격력 저장 

point : index에 해당하는 플레이어의 얻은 포인트 저장

 

n,m,k = map(int,input().split())

graph = [ [[] for _ in range(n)] for _ in range(n)]

for i in range(n):
    tmp = list(map(int,input().split()))
    for j in range(n):
        if tmp[j] :
            graph[i][j].append(tmp[j])

dx = [-1,0,1,0]
dy = [0,1,0,-1]

players = [ [] for _ in range(m+1)] 
board = [ [0] * n for _ in range(n) ]

for i in range(1,m+1):
    x,y,d,s = map(int,input().split())
    x-=1 
    y-=1
    players[i] = [x,y,d,s]
    board[x][y] = i 
    
guns = [0] * (m+1)
point = [0] * (m+1)

def back(num, x,y,d,s):
    
    for i in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            d = (d+1) % 4
            continue 
        
        if board[nx][ny] :
            d = (d+1) % 4
            continue 
        
        board[nx][ny] = num 
        players[num] = [nx,ny,d,s]
        
        if len(graph[nx][ny]) > 0 :
            tmp = max(graph[nx][ny])
            graph[nx][ny].remove(tmp)
            guns[num] = tmp 
        break

def get_gun(num, x,y):
    if len(graph[x][y]) == 0 :
        return 
    if guns[num] > max(graph[x][y]) :
        return 
    
    tmp = max(graph[x][y])
    graph[x][y].remove(tmp)
    if guns[num]:
        graph[x][y].append(guns[num])
    guns[num] = tmp 
                 
def move():
    
    for i in range(1,m+1):
        x,y,d,s = players[i]
        board[x][y] = 0
        nx = x + dx[d]
        ny = y + dy[d]
        nd = d
        if nx < 0 or nx >= n or ny < 0 or ny >= n :
            nd = (d+2) % 4 
            nx = x + dx[nd]
            ny = y + dy[nd]

        # 이동한 위치에 누가 있음 
        if board[nx][ny] :
            p2 = board[nx][ny]
            x2,y2,d2,s2 = players[p2]
            
            # 원래 있던 애가 이김 
            if s2 + guns[p2] > s + guns[i]:
                point[p2] += (s2 + guns[p2]) - (s + guns[i])
                if guns[i]:
                    graph[nx][ny].append(guns[i])
                guns[i] = 0
                back(i,nx,ny,nd,s)
                get_gun(p2, nx, ny)
                
            elif s2 + guns[p2] == s + guns[i] :
                # 원래 있던 애가 이김 
                if s2 > s :
                    if guns[i]:
                        graph[nx][ny].append(guns[i])
                    guns[i] = 0
                    back(i,x2,y2,nd,s)
                    get_gun(p2, nx, ny)
                # 새로 온 애가 이김 
                else :
                    if guns[p2]:
                        graph[nx][ny].append(guns[p2])
                    guns[p2] = 0 
                    back(p2,nx,ny,d2,s2)
                    board[nx][ny] = i 
                    players[i] = [nx,ny,nd,s]
                    get_gun(i, nx, ny)
            else : 
                point[i] += (s + guns[i]) - (s2 + guns[p2])
                if guns[p2]:
                    graph[nx][ny].append(guns[p2])
                guns[p2] = 0 
                back(p2,x2,y2,d2,s2)
                board[nx][ny] = i 
                players[i] = [nx,ny,nd,s]
                get_gun(i, nx, ny)
                
        # 이동한 위치에 누가 없음 
        else :
            # 총이 있으면 
            if len(graph[nx][ny]):
                if max(graph[nx][ny]) > guns[i]:
                    tmp = max(graph[nx][ny])
                    graph[nx][ny].remove(tmp)
                    if guns[i]:
                        graph[nx][ny].append(guns[i])
                    guns[i] = tmp
            board[nx][ny] = i 
            players[i] = [nx,ny,nd,s]
        
for _ in range(k):
    move()
print(*point[1:])