14712_넴모넴모(Easy)

입력

첫째 줄에 가로 길이 N, 세로 길이 M을 입력

출력

연속된 2x2 칸이 채워지지 않은 모든 경우의 수를 출력

조건

• 2x2 칸이 모두 채워지면 안됨

풀이

왼쪽에서 오른쪽, 위에서 아래로 순차적으로 접근하기 때문에 2x2 조건에 대하여 왼쪽 상단([y, x-1], [y-1, x], [y-1, x-1])만 체크

1. map_의 범위를 넘어가지 않기 위해 x+1 < M인 경우 다음에 확인할 좌표는 [y, x+1], x+1 >= M인 경우는 [y+1, 0] 좌표를 다음에 확인

    if x+1 < M:
        dy = y
        dx = x+1
    else:
        dy = y+1
        dx = 0

2. y==0 혹은 x==0일 경우는 확인 순서에 따라 2x2가 만족하는 경우가 없기 때문에 pass, check 함수를 호출하여 2x2 칸이 채워지지 않는지 확인
   => 채워지지 않는 경우는 ans += 1 update하고 map[y][x]를 1로 설정하여 dfs 재귀 호출(넴모를 올린 경우) + 다시 map[y][x]를 0으로 설정하고 dfs 재귀 호출(넴모를 올리지 않은 경우)

def check(y, x, map_):
    if map_[y-1][x] + map_[y][x-1] + map_[y-1][x-1] == 3: return False
    else: return True

def dfs(y, x, map_)
...
...
    if y==0 or x==0 or check(y, x, map_):
        ans += 1
        map_[y][x] = 1
        dfs(dy, dx, map_)
        map_[y][x] = 0
    dfs(dy, dx, map_)

3. y == N일 경우 stop

    if y == N: return

전체 코드

넴모넴모(Easy)