[백준/python]14712번 넴모넴모(Easy) - backtracking

#넴모넴모(easy) , backtraking

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

arr=[ [0 for _ in range(M+1)] for _ in range(N+1) ]
ans=0
def DFS(index_x,index_y):
    global ans
    
    if index_x==N and index_y == M+1 :
        ans+=1
        return
    
    
    if index_y ==M+1:
        index_x+=1
        index_y=1
    
    DFS(index_x, index_y+1)
    
    if arr[index_x -1][index_y]==0 or arr[index_x][index_y-1]==0 or arr[index_x-1][index_y-1]==0:
        arr[index_x][index_y]=1
        DFS(index_x, index_y+1)    
        arr[index_x][index_y]=0
    
DFS(1,1)
print(ans)

“넴모”는 인접한 4칸 중 최대 3칸에만 위치할 수 있다.

1,1에서 윗쪽,왼쪽, 대각선 왼쪽 방향을 체크할 수 있도록 해야한다. 이를 위해 격자판을 나타내는 arr 배열의 가로와 세로에 빈 줄을 하나씩 추가했다.

인접한 3방향에 모두 넴모가 있는 경우를 제외하고 넴모를 배치해가며 백트래킹을 통해 문제를 푼다. 가로 한 줄을 모두 확인하면 y 인덱스에 1을 추가하여 다음 가로로 넘어간다.

격자판 있을 때 index_x, index_y 나눠서 더하지 않고 하나의 변수 index로 통합한 풀이를 발견했다. 행의 마지막 칸에서 다음 행으로 넘어가는 과정 없이 하나의 index에 더해서 행의 개수로 나눈 몫은 x좌표 나머지는 y좌표로 이용할 수 있다.