[코드트리 챌린지] 3주차 - K개 중 하나를 N번 선택하기(Simple)

Backtracking을 더 공부하자!!

3번째 문제에 아직 제대로 공부하지 않은 Backtracking이 나와서 풀지 못했다. 

실력 진단 결과 Backtracking을 공부해야 한다고 나왔다...!

아직 Intermediate Low의 1단원 Simulation만 끝내고 2단원인 Backtracking은 절반만 푼 상태였는데,

역시 진단 결과가 엄청 정확한 것 같다.

 

강력한 폭발 

문제 링크: https://www.codetree.ai/missions/2/problems/strong-explosion?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 1시간 반 좀 넘게 걸린 문제다.

오랜만에 Backtracking을 푸려니 감이 잘 안 잡혔다.

그리고 Backtracking은 계속 재귀호출을 하기 때문에,

코드의 흐름을 파악하기가 힘들어서 조금 어려웠다.

 

아래는 본인이 작성한 테스트케이스를 통과한 정답 코드이다.

n = int(input())
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]
maxCnt = 0

def in_range(i, j):
    return i >= 0 and i < n and j >= 0 and j < n

bombs = []
for i in range(n):
    for j in range(n):
        if grid[i][j] == 1:
            bombs.append([i, j])

dis, djs = [[-2, -1, 1, 2], [-1, 0, 1, 0], [-1, -1, 1, 1]], [[0, 0, 0, 0], [0, 1, 0, -1], [-1, 1, 1, -1]]
def maxExplode(grid, bombs, cnt):
    global maxCnt
    if len(bombs) == 0:
        if cnt > maxCnt:
            maxCnt = cnt
        return

    i, j = bombs[0][0], bombs[0][1]
    for k in range(3): #3종류의 폭탄
        next_grid = [
            grid[i][:] for i in range(n)
        ]
        next_grid[i][j] = 2
        cnt2 = 1
        for index in range(4):
            new_i, new_j = i + dis[k][index], j + djs[k][index]
            if in_range(new_i, new_j) and next_grid[new_i][new_j] == 0:
                next_grid[new_i][new_j] = 2
                cnt2 += 1
        maxExplode(next_grid, bombs[1:], cnt+cnt2)

maxExplode(grid, bombs, 0)
print(maxCnt)

 

 

처음에는 maxExplode함수를 아래와 같이 작성하여 시간 초과로 인해 테스트케이스를 통과하지 못했다.

출력을 통해 확인해 봤더니 원하는 대로 동작을 다 한 다음에, 불필요한 동작을 하고 있었다.

그래서 왜 return이 안되고 불필요한 동작을 추가적으로 하는지에 대해 생각해보았다.

생각해보니 for bomb in bombs로 반복했던게 문제였다.

재귀호출을 하기 때문에 for bomb in bombs로 반복해주면 안된다.

그래서 for bomb in bombs를 지우고, 바로 아래 문장도 그에 맞게 바꾸었더니 정답으로 처리되었다.

def maxExplode(grid, bombs, cnt):
    global maxCnt
    if len(bombs) == 0:
    	#출력을 통해 확인
    	for i in range(n):
        	print(grid[i])
        print()
        if cnt > maxCnt:
            maxCnt = cnt
        return
	
    for bomb in bombs: #잘못된(정답과 다른) 부분
        i, j = bomb[0], bomb[1] #잘못된(정답과 다른) 부분
        for k in range(3): #3종류의 폭탄
            next_grid = [
                grid[i][:] for i in range(n)
            ]
            next_grid[i][j] = 2
            cnt2 = 1
            for index in range(4):
                new_i, new_j = i + dis[k][index], j + djs[k][index]
                if in_range(new_i, new_j) and next_grid[new_i][new_j] == 0:
                    next_grid[new_i][new_j] = 2
                    cnt2 += 1
            maxExplode(next_grid, bombs[1:], cnt+cnt2)