백준 14712번: 넴모넴모(Easy)
백트래킹 문제이다. 처음에는 전체 경우의 수에서 여집합을 빼면 되지 않을까 생각했는데 고민해보니 여집합의 경우의 수를 구하는 게 꽤 까다로웠다. (겹치는 부분이 많아서!) dp나 브루트포스로 풀려고 해도 풀이가 잘 떠오르질 않아서 다른 분들 풀이의 도움을 받았다.
N,M = map(int,input().split())
graph = [[0]*(M+1) for _ in range(N+1)]
ans = 0
def dfs(cnt):
global ans
if cnt == N*M:
ans+=1
return
x = cnt//M +1
y = cnt%M +1
dfs(cnt+1)
if graph[x-1][y] == 0 or graph[x][y-1]==0 or graph[x-1][y-1]==0:
graph[x][y]=1
dfs(cnt+1)
graph[x][y]=0
dfs(0)
print(ans)
위와 같은 풀이인데, 이해한 바로는 다음과 같다.
1)cnt == N*M :전체 칸에 대해 탐색을 완료했다면 ans를 증가시키고 종료
2)cnt//M+1, cnt%M+1 : M=2으로 가정할때 (1,1) (1,2) (2,1) (2,2) ... , M=3으로 가정할때 (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) ...,이런식으로 값이 증가하게 된다. 가로 방향으로 차례로 탐색하는 인덱스 생성
3)dfs(cnt+1) : 다음 인덱스에 대해 dfs -> 해당 칸을 비워두는 경우
4)if ~ : 해당 칸을 채웠을 때 넴모넴모가 생성되지 않는다면 칸을 채운 후에 dfs를 실행하고, 이후에 x,y를 다시 0으로 초기화해준다.
즉, 각 칸을 채우거나/채우지 않는 경우를 선택했을 때 넴모넴모가 만들어지지 않는 모든 경우의 수를 탐색하는 것이다. (해당 칸을 채웠을때 넴모넴모가 만들어진다면 이 부분 경우의 수에 대해서는 아예 생략하게 되는 것) 이를 통해서 결과를 구할 수 있는데, 하나하나 다 구하는 방식이다 보니 Python3에서는 시간초과가 뜬다. 그래서 pypy3으로 하면 통과가 되는데, python3으로는 그러면 어떻게 푸나해서 공개된 풀이를 확인해보니 그냥 1,1~5,5까지의 정답을 전부 써둔 방식이었다(...) 아마 python3으로는 시간 초과가 뜨는 문제인 듯 하다.
