[백준 18430번] 무기공학(파이썬)

https://www.acmicpc.net/problem/18430

18430번: 무기 공학

 

처음 이 문제를 보고

'와 개 쉽네'

라고 신나게 구현했다가

예제를 통과하지 못했습니다.

처음에는 dfs로 한칸씩 이동하다가

3칸째 이동했을때

여태까지 이동한 칸 합의 최대를 구하는 줄 알았습니다.

그런데...얼라라?

부메랑을 만든 것의 총합??

 

x된 칸에 부메랑을 넣는다가정하면

저렇게 1,2,3의 케이스가 있습니다.

저렇게 채우면 더이상 채울 수 없으니

그때의 합을 구합니다.

백트레킹으로 전체의 부메랑을 다 넣고

그 때의 합을 구한다라...

처음엔 머리가 아팠다가

백트레킹의 원리를 생각하면서 코드를 작성했습니다.

#백준 18430번 무기공학

N,M=map(int,input().split())

room=[list(map(int,input().split()))for _ in range(N)]
boomarage=[
    [[0,-1],[1,0]],
    [[-1,0],[0,-1]],
    [[-1,0],[0,1]],
    [[1,0],[0,1]]
]

answer=0
hap=0
visited=[[False]*M for _ in range(N)]

def dfs():
    global answer
    global hap
    for x in range(N):
        for y in range(M):
            if visited[x][y]==False:
                for shape in boomarage:
                    put=[]
                    center=room[x][y]*2
                    for px,py in shape:
                        nx=x+px
                        ny=y+py
                        if nx<0 or nx>=N or ny<0 or ny>=M:
                            put.clear()
                            break
                        if visited[nx][ny]==True:
                            put.clear()
                            break

                        put.append([nx,ny])

                    if put:
                        hap+=center
                        visited[x][y]=True
                        for ux,uy in put:
                            visited[ux][uy]=True
                            hap+=room[ux][uy]
                        dfs()
                        for ux,uy in put:
                            visited[ux][uy]=False
                            hap-=room[ux][uy]
                        visited[x][y]=False
                        hap-=center

    answer=max(answer,hap)
    return



dfs()
print(answer)

처음에 작성한 코드입니다.

shape라는 리스트에

각 모양에 대한 정보를 받아줍니다.

center는 무게가중이 2배로 해주고요.

x,y를 탐색하다가

비어있는 부분에다가 부메랑을 대봅니다.

이 때, 범위를 벗어나거나 다른 것과 겹치면 아웃.

그때의 부메랑 합을 더해서 dfs로 넘겨줍니다.

그런데 이 방식은 시간초과가 걸렸습니다.

로직은 맞긴하는데...

컴퓨터에서 처리하는 시간이 너무 길었습니다.

이 부분은 구글링으로 도움을 얻어 수정했습니다.

 

#백준 18430번 무기공학

N,M=map(int,input().split())

room=[list(map(int,input().split()))for _ in range(N)]
boomarage=[
    [[0,-1],[1,0]],
    [[-1,0],[0,-1]],
    [[-1,0],[0,1]],
    [[1,0],[0,1]]
]

answer=0

visited=[[False]*M for _ in range(N)]

def dfs(hap,x,y):
    global answer
    if y==M:
        y=0
        x+=1
    if x==N:
        answer = max(answer, hap)
        return
    if visited[x][y]==False:
        for shape in boomarage:
            put=[]
            center=room[x][y]*2
            for px,py in shape:
                nx=x+px
                ny=y+py
                if nx<0 or nx>=N or ny<0 or ny>=M:
                    put.clear()
                    break
                if visited[nx][ny]==True:
                    put.clear()
                    break

                put.append([nx,ny])

            if put:
                visited[x][y]=True

                for ux,uy in put:
                    visited[ux][uy]=True

                dfs(hap+center+room[put[0][0]][put[0][1]]+room[put[1][0]][put[1][1]],x,y+1)
                visited[x][y]=False
                for ux,uy in put:
                    visited[ux][uy]=False
    dfs(hap,x,y+1)




dfs(0,0,0)
print(answer)

dfs해주면서

x,y좌표를 이동시켰습니다.

부메랑을 만들든 만들지 않든간에

dfs를 해주는 것이 포인트.

이렇게 구현해야지 시간초과에 걸리지 않았습니다.

처음 방식대로 이중for문을 구현하면

이동할 때마다 이중for문을 계속 건드려야하니

시간초과가 났던 것 같습니다.

 

https://comdolidol-i.tistory.com/313

[파이썬][백준 18430][백트래킹] 무기공학 - 컴도리돌이

참고한 코드입니다.

 

백트래킹 문제를 풀 때

좌표이동에 대한 공부를 할 수 있었습니다.