알고리즘 풀이 백준(BOI) 19236) 청소년 상어 (Python)

백준(BOI) 19236 - 청소년 상어

---

 

19236번: 청소년 상어

 

[문제풀이]

 

 청소년 상어가 먹을 수 있는 물고기의 최대값을 구하는 문제이다.

 

 상어의 진행 방향 중 물고기가 있으면 해당 물고기의 방향을 복사해오며 새로운 길이 뚫리기에 DFS로 풀었다.

 

 재귀 할 때마다 그리드를 깊은복사를 하여 원본 그리드의 수정을 방지하였다. 

 

 DFS는 종료조건을 명확히 해주어 스택오버플로우를 방지하는게 핵심인 것 같다.

 

 파이썬에 입문한지 한 달 밖에 되지 않아 코드를 작성하는데 익숙치 않아 미흡한 점이 많다. 양해 바란다. 

 

 

 

 

 

 문제에서 주어진 로직은 다음과 같다.

 

1. 상어가 0, 0 칸에 들어온다. 상어는 0, 0 칸에 있던 물고기의 방향을 복사한다.
2. 물고기가 가진 방향으로 작은번호부터 순서대로 이동한다.
3. 물고기가 이동을 마치면 상어가 방향으로 이동한다.
4. 이동방향에 물고기가 있으면 그 물고기를 먹으며 그 물고기의 방향을 복사한다.
5. 물고기를 먹지 않고 다음 물고기가 있는 지역으로 이동 할 수 있다.
6. 상어의 이동방향에 물고기가 없으면 상어는 집으로 돌아간다 (종료된다).

 "물고기를 먹지 않고 다음 물고기가 있는 지역으로 이동 할 수 있다." 라는 구문 때문에 경우의수가 굉장히 많아지게 된다.

 

 먹을 수 있는 물고기의 최대값을 구하는 문제이므로 종료조건을 잘 주어 깊이우선탐색을 실행하면 쉽게 풀 수 있다고 생각하였다.

 

 메모리와 시간을 걱정하지 않고 일단 제출하였는데 다행히 무난히 통과하였다.

 

 

 

 

---

[전체 소스코드]

def deepcopy(objgrid, dirgrid):
    copyobjgrid = [[0 for _ in range(4)]for _ in range(4)]
    copydirgrid = [[0 for _ in range(4)]for _ in range(4)]    
    for i in range(4):
        for j in range(4):
            copyobjgrid[i][j] = objgrid[i][j]
            copydirgrid[i][j] = dirgrid[i][j]
            
    return copyobjgrid, copydirgrid
    
def checkValid(nowx, nowy, objgrid, nowdir):
    global directions
    dx, dy = directions[nowdir]
    valid = False
    while True:
        nextx = nowx + dx
        nexty = nowy + dy
        if nextx >= 4 or nexty >= 4 or nextx < 0 or nexty < 0:
            break
        if objgrid[nextx][nexty] > 0:
            valid = True
        nowx = nextx
        nowy = nexty
    return valid

def move(objgrid, dirgrid):
    global directions
    copyobjgrid, copydirgrid = deepcopy(objgrid, dirgrid)
    index = 1
    while index <= 16:
        oper = False
        for i in range(4):
            for j in range(4):
                if copyobjgrid[i][j] == index and oper == False:
                    oper = True
                    nowdir = copydirgrid[i][j]
                    while True:
                        dx, dy = directions[nowdir]
                        nextx = i + dx
                        nexty = j + dy
                        if nextx < 0 or nexty < 0 or nextx >= 4 or nexty >= 4 or copyobjgrid[nextx][nexty] == -1: 
                            nowdir += 1
                            if nowdir == 9: nowdir = 1
                            if nowdir == copydirgrid[i][j]: break
                            continue
                        temp = copydirgrid[nextx][nexty]
                        copydirgrid[nextx][nexty] = nowdir
                        copydirgrid[i][j] = temp
                        temp = copyobjgrid[nextx][nexty]
                        copyobjgrid[nextx][nexty] = copyobjgrid[i][j]
                        copyobjgrid[i][j] = temp
                        break
                    
        index += 1
    return copyobjgrid, copydirgrid

def go(nowx, nowy, sumresult, objgrid, dirgrid):
    global directions, maxresult
    firstx, firsty = nowx, nowy
    copyobjgrid, copydirgrid = deepcopy(objgrid, dirgrid)
    copyobjgrid[nowx][nowy] = -1
    copyobjgrid, copydirgrid = move(copyobjgrid, copydirgrid)

    if not checkValid(nowx, nowy, copyobjgrid, copydirgrid[nowx][nowy]):
        maxresult = max(maxresult, sumresult)
        return
    dx, dy = directions[copydirgrid[nowx][nowy]]
    while True:
        nextx = nowx + dx
        nexty = nowy + dy
        if nextx >= 4 or nexty >= 4 or nextx < 0 or nexty < 0:
            break
        if copyobjgrid[nextx][nexty] > 0:
            copyobjgrid[firstx][firsty] = 0
            go(nextx, nexty, sumresult + copyobjgrid[nextx][nexty], copyobjgrid, copydirgrid)
            copyobjgrid[firstx][firsty] = -1
        nowx = nextx
        nowy = nexty
        
    
    
    
    
objgrid = [[0 for _ in range(4)]for _ in range(4)]
dirgrid = [[0 for _ in range(4)]for _ in range(4)]
directions = (0, 0), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)
maxresult = 0

for i in range(4):
    inputstr = list(map(int,input().split()))
    index = 0
    for j in range(4):
        objgrid[i][j] = inputstr[index]
        index += 1
        dirgrid[i][j] = inputstr[index]
        index += 1


go(0, 0, objgrid[0][0], objgrid, dirgrid)
print(maxresult)