[백준/파이썬(Python)] 넴모넴모 14712 Silver 1

💌문제

---

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

14712번: 넴모넴모 (Easy)

💌풀이

---

 

[BOJ] 14712 넴모넴모 - Python

[BOJ] 14712 넴모넴모 - Python

백준 14712번 넴모넴모 (Easy) : 파이썬

백준 14712번 넴모넴모 (Easy) : 파이썬

이해하기 위해 겁나 많이 찾아봄… 제대로 이해한게 맞는지도 확실하진 않다. 틀렸을 수도 있다.

DFS를 사용해야 한다.

왜냐면 일단 이 문제는 완전탐색을 이용해서 모든 맵을 탐색하면서 22 넴모넴모가 생기는 경우를 빼줘야 한다.

즉, 모든 경우의 수에서 22넴모넴모가 생기는 경우를 빼줘야 하는 문제이다.

그런데 정말로 완전탐색으로 모든 맵에 넴모넴모를 넣어주면서 2*2가 생기는지 안 생기는지를 체크하면 시간초과가 발생하게 된다.

그래서 백트래킹을 이용해서 맵을 탐색하다가, 만약 2*2 넴모넴모가 생기면 다시 되돌아와서 다음 범위를 탐색하도록 한다.

다시말해, 2*2 넴모넴모가 생기면 그 다음 범위부터는 이미 전부 다 안되니까 탐색하지 않고 되돌아 가는 것이다.

(x,y)에 넴모를 넣는 경우와 안 넣는 경우로 나눠서 dfs를 진행한다.

넴모를 넣으면 상단, 좌측, 좌상단 중 하나라도 넴모가 없어야 2*2 넴모넴모가 생기지 않으니까 조건문을 이용해서 하나라도 넴모가 없으면 넴모를 현재 (x,y)에 넣는다. 넣고나서 dfs를 진행한다.

dfs를 진행할 때는 항상 깊이를 1씩 늘려줘야 한다. 넴모를 넣든 안 넣든 다음 격자판을 dfs를 시행하면 다음을 확인하기 때문이다.

그리고 종료 조건은 깊이가 n*m 즉, 격자판의 크기가 될 때 종료한다. 왜냐면 거기까지 도달하면 해당 격자판은 2*2넴모넴모가 안 생겼다는 뜻이기 때문에 경우의 수를 추가할 수 있다.

 

x와 y좌표는 현재 깊이/열의 길이+1와 현재 깊이%열의 길이+1로 나타낼 수 있다. 왜냐면 일단 y좌표 같은 경우 나머지 연산을 통해 열의 길이로 모듈러 연산하게 되면 0~m-1로 나타낼 수 있다. 그런데 인덱스를 1부터 시작해서 m까지 나타내야 하니까 거기에 1을 더해주면 1~m까지 나타낼 수 있다. 즉, 모듈러 연산을 이용해서 y좌표를 다 설정하고 탐색할 수 있게 된다.

x좌표 같은 경우 나누기 연산을 이용하는데, 나누기 연산을 해주게 되면 현재 행에서 열을 우선적으로 다 보고 나면 하나씩 나누어 지는 수가 늘어나게 된다. 즉, 2중 포문을 돌릴 때처럼 열을 먼저 다 보고 그 뒤에 행을 1씩 늘려줘서 다시 그 행에서 열을 다 확인하는 식으로 체크해줄 수 있다. 그런데 x좌표도 인덱스가 1부터 시작해야 해서 1을 더해주는 것이다.

그래서 깊이가 늘어날 때마다 그 깊이를 가지고 좌표를 설정하여 탐색한다.

 

하.. 백트래킹이랑 dfs가 너무 어렵다.

 

💌자바 코드

---

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

def dfs(depth):
    global answer
    if(depth==n*m):
        answer+=1
        return
    x=depth//m+1
    y=depth%m+1

    if(nemo[x-1][y]==0 or nemo[x-1][y-1]==0 or nemo[x][y-1]==0):
        # 넴모를 놓을 수 있는 경우
        nemo[x][y]=1
        dfs(depth+1)
        nemo[x][y]=0 #되돌아오면 다시 0
    dfs(depth+1) # 넴모를 안 놓음

dfs(0)
print(answer)