[BOJ] 14712 넴모넴모 - Python

문제

---

 

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

14712번: 넴모넴모 (Easy)

풀이

---

위 문제를 처음 봤을 때 전체의 경우에서 넴모가 2X2 사각형을 이루는 경우를 뺀 값을 답으로 구하려 했습니다. 즉 여집합 개념을 사용하여 답을 구해보려 했는데 생각보다 여집합을 구하는 과정이 복잡하다고 생각하여 시도 중 다른 풀이로 전환하였습니다. 

 

풀이 전환 과정이 좀 더 빨랐다면 좋았을 텐데 힌트를 보고 여집합에 꽂혀버려서 시간을 조금 많이 보낸 것 같습니다.

 

왜 여집합을 구하는 과정이 어려웠는가..?

• 2X2 사각형을 좌측 상단부터 우측 하단까지 넣어보고 각각 경우에 대해 몇 가지 종류의 격자판이 생기는지 세어봤습니다.
    ➡ 이 경우들을 세면 여집합의 총 개수를 구할 수 있을 것이라 생각했음.
• 이때 각각 경우가 독립적이지 않고 서로 겹치는 경우가 생겨 이에 대한 체크가 필요했습니다.
• 그런데 겹치는 경우가 너무 많아 맵이 커지면 감당이 되지 않을 것 같아 규칙 찾기를 포기했습니다. 

 

그래서 다음 풀이로 생각한 것이 DFS를 이용한 완전 탐색이었습니다. 문제에서 주어진 입력 크기가 충분히 작아 보였고 이에 모든 경우를 세어보는 것이 가능하다고 생각했습니다.

 

주요 로직은 DFS 함수가 거의 전부이므로 작성한 DFS 함수 위주로 설명하겠습니다.

• DFS 함수에 대한 설명은 아래와 같습니다.
  • (x, y) 에 넴모를 넣는 경우와 안 넣는 경우로 나눠 DFS를 진행했습니다. 이때 넴모를 넣는 경우는 좌측, 상단, 좌상단 중 하나라도 넴모가 없어야 2X2 넴모 사각형이 생기지 않으므로 이를 체크해줍니다.
  • DFS는 (1, 1)에서부터 x축 방향으로 진행하여 (m, n) 까지 진행했습니다. ( 글 쓰는 방향 )
  •  (x , y) = (1, n + 1)이 될 때, 즉 2X2 넴모 사각형 없이 격자판을 전부 채운 상황에 도달한 경우 count에 1을 더해줍니다. 

 

풀이 코드는 아래와 같습니다.

n, m = map(int, input().split())
graph = [[0] * (m + 1) for _ in range(n + 1)]
count = 0

def dfs(x, y):
    global count
    # 종료 조건
    if (x, y) == (1, n + 1):
        count += 1
        return
    
    if x == m:
        nx, ny = 1, y + 1
    else:
        nx, ny = x + 1, y
        
    # x, y에 네모를 놓지 않은 경우
    dfs(nx, ny)
    
    # x, y에 네모를 놓을 수 있고 놓는 경우
    if graph[y - 1][x] == 0 or graph[y - 1][x - 1] == 0 or graph[y][x - 1] == 0:
        graph[y][x] = 1
        dfs(nx, ny)
        graph[y][x] = 0
        
dfs(1, 1)

print(count)