[삼성sw 5644번]무선충전(파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

SW Expert Academy

상당히 독특했던 문제.

우선 문제 푸는 순서는 이렇게 됩니다.

 

1. 기지국 범위 설정

-->저는 []를 10*10만큼 불러내주고

기지국의 범위에 해당 기지국 번호를 append해줬습니다.

이렇게 해야, 차후에 기지국이 겹칠 때

해당 지역에 어떤 기지국들이 있는지 볼 수 있습니다.

 

2. 지나가면서 충전값 구하기

-->저는 a가 b가

a 충 b x

a x   b 충

a 충 b 충

이렇게 3가지로 나눠서 구했습니다.

a b 둘 다 충전이 가능하다면

두 지점에 있는 각각의 기지국을 받습니다.

만약, a와 b의 기지국이 같다면

현재 충전가능한 값은 기지국 하나의 값

(두 개가 들어가면 둘을 나눈 값이 되므로)

그렇게 현재 충전값이

a b 조합에서 최대값인지 여부를 확인해주고

그 최대값을 돌립니다.

 

하지만 이 문제는 낚시조건이 2가지있습니다.

 

1. t=0일때 고려해준다.

처음에 테케 통과가 안되서

문제를 다시 읽어보니

T=0일때도 구하는 표가 있었습니다.

아...초기에 가만히 있을때도 고려해줘야해?

그래서 a,b각각 움직임을 받는 리스트 앞에

0을 추가해줬습니다.

 

2. 기지국의 좌표

저는 프로그래밍을 연습하면서부터

x값은 세로

y값은 가로로 받는데에 익숙해져있습니다.

(저도 처음엔 

실생활에서 처럼

x 가로,y 세로로 받다가

문제 해설들이랑 자꾸 충돌해서

그냥 저렇게 머리에 박았습니다.)

그래서 이 문제는

기지국 좌표에서 조금 헤멨습니다.

기지국 범위를 bfs로 해줬는데

어라??왜 내 결과값은 예제랑 다르지??

하고 꼼꼼히 읽어보다가

가로랑 세로가 바뀌었습니다.

이건 bfs할 때 가로,세로를 서로 변경해주면서 고쳤습니다.

 

이외에 들여쓰기 하나 잘못해서

테케 맞왜틀.

그리고 a b 둘 다 충전이 안되어있을때

실수로 이전의 충전값을 넣어주는 코드가 있어서 수정.

(저는 현재 충전값을 tmp로 받아줬는데

tmp를 움직일때마다 초기화를 해주지 않으면

둘 다 충전이 없을 때

이전값이 들어가는 일이 생기더라고요)

그리고 이건 의외로 저도 많이 실수하는 부분인데

방향키 설정할 때

문제대로 체크했는지 확인 필수.

 

#삼성sw 무선 충전
from collections import deque
dx=[0,-1,0,1,0]
dy=[0,0,1,0,-1]

def bfs(sx,sy,md,num):
    q=deque()
    q.append((sx,sy,0))
    visited=set()
    visited.add((sx,sy))
    room[sx][sy].append(num)
    while q:
        x,y,nd=q.popleft()
        if nd>=md:
            continue

        for d in range(1,5):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=10 or ny<0 or ny>=10:
                continue

            if (nx,ny) in visited:
                continue

            q.append((nx,ny,nd+1))
            room[nx][ny].append(num)
            visited.add((nx,ny))




T=int(input())

for t in range(T):
    answer=0
    M,A=map(int,input().split())
    room=[[[]for _ in range(10)] for _ in range(10)]

    ax,ay=0,0
    bx,by=9,9
    #a,b가 처음에 가만히 있는 경우도 생각해줘야한다
    a_move=[0]+list(map(int,input().split()))
    b_move = [0]+list(map(int, input().split()))
    B_C=[0]*(A+1)
    #1. 기지국 범위
    for k in range(1,A+1):
        cx,cy,cd,cpack= map(int, input().split())
        cx-=1
        cy-=1
        bfs(cy,cx,cd,k)
        B_C[k]=cpack
    #print(room)
    #2.이동해주면서 최대값 구하기
    for d in range(M+1):
        tmp=0
        #A B 이동
        na=a_move[d]
        ax+=dx[na]
        ay+=dy[na]

        nb=b_move[d]
        bx+=dx[nb]
        by+=dy[nb]

        #현지점에서 어떻게 겹치는지 케이스 구하기
        #a만 있는 경우
        if room[ax][ay] and not room[bx][by]:
            a_a=[]
            for pack in room[ax][ay]:
                n_a=B_C[pack]
                a_a.append(n_a)

            tmp=max(a_a)
        #b만 있는 경우
        elif not room[ax][ay] and room[bx][by]:
            b_a = []
            for pack in room[bx][by]:
                n_b = B_C[pack]
                b_a.append(n_b)

            tmp= max(b_a)
        #둘다있는 경우
        elif room[ax][ay] and room[bx][by]:
            a_num=[]
            b_num = []

            for pack in room[ax][ay]:
                a_num.append(pack)
            for pack in room[bx][by]:
                b_num.append(pack)

            t_max=-1
            for i in range(len(a_num)):

                x=a_num[i]
                for j in range(len(b_num)):
                    y=b_num[j]

                    if x==y:
                        hap=B_C[x]
                    else:
                        hap=B_C[x]+B_C[y]
                    # print(d, x, y, B_C[x], B_C[y],hap,t_max)

                    #들여쓰기 실수한 부분....
                    if hap>t_max:
                        t_max=hap


            tmp=t_max
        # print(d,tmp)
        answer+=tmp

    print("#%d %d"%(t+1,answer))

 

bfs를 적용할 수 있는 좋은 문제로

기지국 범위 겹치는 부분을 어떻게 처리할지가

좋은 공부 포인트였습니다.