[삼성sw 5650] 핀볼게임(파이썬)

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

SW Expert Academy

이 문제는....

좀 빡이 많이 쳤던 문제.

시간초과 이슈를 어떻게 줄일까...

연구를 많이 하게 된 문제.

 

우선, 저는 이 문제를 dp로 접근하려고 했습니다.

좌표 하나 하나 다 상하좌우로 핀볼을 굴릴 때를 고려하면

100% 시간초과가 뜰 게 분명했습니다.

그래서 dp에 '해당 지점에서 상하좌우로 갈 때

최대값은 이거다'라는 걸 받아보려고 했습니다.

막상 구현해보니 원하는 값이 안나왔어요.

왜 이럴까 생각했는데

상당히 심플한 이유였습니다.

만약 어떤 지점에서

오른쪽으로 갈떄의 dp값이

3이라고 가정해보겠습니다.

그런데 이 3이 어떻게 3인지 알 수가 없습니다.

이게 블랙홀에 들어가서 3이라면

dp값과 현재 cnt를 더해야하고

벽을 치고 돌아온 경우라면

dp값+현재 cntx 2값을 해야합니다.

그런데 dp만으로는 이 두가지를 구분하기 쉽지 않았습니다.

(굳이 구분한다면 블랙홀일떄와

벽팅기기 2가지를 구분하는 건데...

이걸 저장하는 게 또 난관이니

배보다 배꼽이 더 큰 느낌)

 

그래서 그냥 빡구현으로 구했는데...

시간초과뜬 코드입니다.

 

from collections import deque

T=int(input())
dx=[-1,0,1,0]
dy=[0,1,0,-1]

def bfs(sx,sy,md):
    now_max=0

    x,y,d=sx,sy,md
    cnt=0

    while True:

        if x==sx and y==sy and cnt>0:
            #print('f')
            now_max=max(now_max,cnt)
            break


        nx=x+dx[d]
        ny=y+dy[d]



        if nx<0 or nx>=N or ny<0 or ny>=N:

            d=(d+2)%4
            nx=x
            ny=y
            cnt+=1



        if room[nx][ny]==0:
            x,y=nx,ny

        elif room[nx][ny]==-1:

            now_max=max(now_max,cnt)
            break
        #4각형 블록
        elif room[nx][ny]==5:
            x,y=nx,ny
            d=(d+2)%4
            cnt+=1
        elif 6<=room[nx][ny]<=10:

            whole=room[nx][ny]
            for wx,wy in warm_hole[whole]:
                if wx==nx and wy==ny:
                    continue
                nx=wx
                ny=wy
                break

            x, y = nx, ny

        #방향이 바뀌는 경우들
        elif d==0:
            if room[nx][ny]==2:
                d=1
                x, y = nx, ny
                cnt+=1
            elif room[nx][ny]==3:

                d=3
                x, y = nx, ny
                cnt+=1
            elif room[nx][ny]==1 or room[nx][ny]==4:

                d=2
                x, y = nx, ny
                cnt+=1
        elif d==1:
            if room[nx][ny]==3:
                d=2
                x, y = nx, ny
                cnt+=1

            elif room[nx][ny]==4:
                d=0
                x, y = nx, ny
                cnt+=1

            elif room[nx][ny]==1 or room[nx][ny]==2:
                d=3
                x, y = nx, ny
                cnt+=1

        elif d==2:
            if room[nx][ny]==4:
                d=3
                x, y = nx, ny
                cnt+=1

            elif room[nx][ny]==1:
                d=1
                x, y = nx, ny
                cnt+=1

            elif room[nx][ny]==2 or room[nx][ny]==3:
                d=0
                x, y = nx, ny
                cnt+=1


        elif d==3:
            if room[nx][ny]==1:
                d=0
                x, y = nx, ny
                cnt+=1

            elif room[nx][ny]==2:
                d=2
                x, y = nx, ny
                cnt+=1

            elif room[nx][ny]==3 or room[nx][ny]==4:
                d=1
                x, y = nx, ny
                cnt+=1


    return now_max

for t in range(1,T+1):
    N=int(input())
    room=[]
    warm_hole=[[]for _ in range(11)]
    for i in range(N):
        tmp=list(map(int,input().split()))
        for j in range(N):
            if 6<=tmp[j]<=10:
                warm_hole[tmp[j]].append((i,j))
        room.append(tmp)


    answer=0
    for x in range(N):
        for y in range(N):
            if room[x][y]==0:
                for d in range(4):
                    answer=max(answer,bfs(x,y,d))
    print("#%d %d"%(t,answer))

구현은 나름 맞았는데

시간초과가 떴습니다.

이유를 구글링해서 찾아보니

웜홀에서 텔포해줄 때랑

벽만나서 바꿔주는 부분에서

시간을 많이 잡아먹었습니다.

웜홀은 미리미리 좌표값을 구한다음 움직여주는 방식이 있고

벽을 만나는 건 미리미리 바뀌는 방향을 저장하는 방식이 있었죠.

그리고 좌표를 벗어나는 지점은 벽을 5로 채워두면

굳이 따로 범위를 벗어날 때를 따로 구현할 필요없이

간단하게 1~5의 숫자를 만날 때만 구현하면 됩니다.

 

T=int(input())
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

change_dir = ((),
              (1, 3, 0, 2),
              (3, 0, 1, 2),
              (2, 0, 3, 1),
              (1, 2, 3, 0),
              (1, 0, 3, 2))

def bfs(sx,sy,md):
    global wormhole_info
    score = 0
    x,y=sx,sy       # 시작 위치 저장
    d=md
    while True:
        x += dx[d]      # 이동하면서 시작해야 함
        y += dy[d]
        # 출발 위치로 돌아오거나 블랙홀 만나면 게임 끝. 점수 리턴
        if (x, y) == (sx, sy) or room[x][y] == -1:
            return score
        if 1 <= room[x][y] <= 5:           # 블록 만나면 방향 바꾸고 점수 + 1
            d = change_dir[room[x][y]][d]
            score += 1
        elif 6 <= room[x][y] <= 10:        # 웜홀 만나면 같은 번호의 웜홀로 이동. 방향은 유지
            x, y = wormhole_info[(x, y)]

for t in range(1,T+1):
    N=int(input())
    room=[[5]*(N+2)]
    wormhole_check = [0] * 11
    wormhole_info = dict()  # 웜홀 쌍 정보

    for i in range(1,N+1):
        tmp=[5]+list(map(int,input().split()))+[5]
        for j in range(N+2):
            if 6<=tmp[j]<=10:
                num = tmp[j]
                if not wormhole_check[num]:
                    wormhole_check[num] = (i, j)
                else:  # 같은 번호 웜홀끼리 위치 정보 저장
                    wormhole_info[wormhole_check[num]] = (i, j)
                    wormhole_info[(i, j)] = wormhole_check[num]
        room.append(tmp)

    room.append([5] * (N + 2))

    answer=0
    for x in range(1,N+1):
        for y in range(1,N+1):
            if room[x][y]==0:
                for d in range(4):
                    answer=max(answer,bfs(x,y,d))
    print("#%d %d"%(t,answer))

 

시간초과관점에서 공부할 것이 많았던 문제입니다.

시간을 어떻게 세이브할 지 고민에 또 고민...