문제링크

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

풀이

주의사항: X,Y 좌표계가 보통 문제와 다르니 주의

1. BFS를 활용해 3차원 배열을 활용해 충전기의 위치를 나타낸다.

문제예시)

[[], [], [], [], [], [], [], [], [], [], []] [[], [], [], [], [], [], [2], [], [], [], []] [[], [], [], [], [], [2], [2], [2], [], [], []] [[], [], [], [], [0, 2], [2], [2], [2], [2], [], []] [[], [], [], [0], [0], [0, 2], [2], [2], [], [], []] [[], [], [], [], [0], [], [2], [], [], [], []] [[], [], [], [], [], [], [], [], [], [], []] [[], [], [], [], [], [], [], [1], [], [], []] [[], [], [], [], [], [], [1], [1], [1], [], []] [[], [], [], [], [], [1], [1], [1], [1], [1], []] [[], [], [], [], [1], [1], [1], [1], [1], [1], [1]]

1. A,B를 이동시키면서 같은 충전기 범위에 있는지 검사하면서 최대충전량을 2중 포문으로 구한다.

코드

from collections import deque
cnum = int(input())
dx=[0,-1,0,1,0]
dy=[0,0,1,0,-1]
class Player:
    def __init__(self,x,y,charge):
        self.x=x
        self.y=y
        self.charge=charge
ans=[]
for tcase in range(1,cnum+1):
    board = [[[] for _ in range(11)] for _ in range(11)]
    m,a = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    ap=[]
    #BFS 로 충전기 위치 표시
    def markBoard(x,y,p,c):
        if p not in board[x][y]:
            board[x][y].append(p)
        q = deque()
        q.append([x,y])
        while q:
            a,b=q.popleft()
            for i in range(1,5):
                nx=dx[i]+a
                ny=dy[i]+b
                if 1<=nx<=10 and 1<=ny<=10 and abs(x-nx)+abs(y-ny)<=c:
                    if p not in board[nx][ny]:
                        board[nx][ny].append(p)
                        q.append([nx,ny])
    bclist =[]
    for i in range(a):
        x,y,c,p = map(int,input().split())
        markBoard(y,x,i,c)
        bclist.append(p)
        
    a=Player(1,1,0)
    b=Player(10,10,0)
    A=[0]+A
    B=[0]+B
    answer=0
 
  
    for i in range(m+1):
        a.x=a.x + dx[A[i]]
        a.y=a.y + dy[A[i]]
      
        b.x=b.x + dx[B[i]]
        b.y=b.y + dy[B[i]]
        charge=0
        # A와 B모두 충전할 수 있는 경우
        if board[a.x][a.y] and board[b.x][b.y]:
            for x in range(len(bclist)):
                for y in range(len(bclist)):
                    if x in board[a.x][a.y] and y in board[b.x][b.y]:
                        if x==y:
                            charge=max(charge,bclist[x])
                        else:
                            charge=max(charge,bclist[x]+bclist[y])
        # 한쪽만 충전 가능한 경우               
        elif board[a.x][a.y]:
            for x in range(len(bclist)):
                if x in board[a.x][a.y]:
                    charge=max(charge,bclist[x])
        elif board[b.x][b.y]:
            for x in range(len(bclist)):
                if x in board[b.x][b.y]:
                    charge=max(charge,bclist[x])
        answer+=charge
    print(f"#{tcase} {answer}")
    ans.append(answer)