[BOJ/백준] 1553 도미노 찾기 파이썬

문제 링크 : https://www.acmicpc.net/problem/1553

1553번: 도미노 찾기

 

도미노를 놓는 방향은 ㅡ ㅣ 두가지 모양밖에 없다.

(0,0)부터 두 방향으로 묶어서  백트래킹으로 완탐해보자.

 

도미노를 (0,0)에서 (7,6)까지 순차적으로 확인하면 되므로 왼쪽이나 오른쪽을 향하도록 놓지 않아도 된다.

그래서 나는 처음에 오른쪽방향으로 도미노를 만들어 보고 다음 아래쪽 방향으로 도미노를 만들어 봤다.

 

이때 이미 사용한 도미노인지, 해당방향의 칸에 번호를 다른 도미노에서 사용했는지 확인해야한다.

나는 used 2차원 배열, visited 2차원 배열 두개를 사용 했다.

used는 해당 숫자 조합의 도미노의 사용 여부이다.

visited는 해당 칸을 도미노를 만드는데 사용했냐이다.

 

이제 (0,0)부터 확인하자.

 

만약 현재 칸이 방문한 칸이라면 바로 옆칸으로 이동하자.

 

그렇지 않다면 도미노를 만들어본다.

우선 현재칸을 방문 표시해주자.

그리고 현재칸의 숫자와 다음 칸의 숫자의 조합인 도미노를 사용했는지와 다음칸을 방문했는지를 체크한다.

만약 둘다 통과한다면 used와 visited를 갱신하자.

이때 used는 (0,1)과 (1,0)은 같은 도미노 이므로 함께 바꿔주자.

 

마지막으로 모든칸을 확인했는지를 체크한다.

이것은 현재 점의 x좌표가 8인지 체크하면 된다.

 

from sys import stdin

input = stdin.readline

board = [list(map(int, list(input().strip()))) for _ in range(8)]
used = [[False]*7 for _ in range(7)]
visited = [[False]*7 for _ in range(8)]

def solv():
    print(go(0,0))

def go(x,y):
    global used,visited
    if x == 8:
        return 1
    count = 0
    nnx = x
    nny = y + 1
    if nny == 7:
        nnx = x + 1
        nny = 0
    if visited[x][y]:
        return go(nnx,nny)
    else:
        now = board[x][y]
        visited[x][y] = True
        for dx,dy in ((0,1),(1,0)):
            nx = x + dx
            ny = y + dy

            if boundray_validator(nx,ny):
                nxt = board[nx][ny]

                if not used[now][nxt] and not visited[nx][ny]:
                    used[now][nxt] = used[nxt][now] = True
                    visited[nx][ny] = True
                    count += go(nnx,nny)
                    visited[nx][ny] = False
                    used[now][nxt] = used[nxt][now] = False
        visited[x][y] = False
        return count

def boundray_validator(x,y):
    if x >= 8 or y >= 7:
        return False
    return True
solv()