[백준] 4574번 : 스노미노쿠

4574번: 스도미노쿠

4574번: 스도미노쿠

🤔 문제분석

완전탐색과 구현 유형의 문제로, 모든 타일의 경우(방문하지 않은)를 가로방향, 세로방향을 놓아보면서 문제를 해결 하였습니다.

💻 코드

import sys
input = sys.stdin.readline

def get_pos(LU):
    y, x = ord(LU[0]) - ord('A'), int(LU[1])-1
    return y, x

def is_range(y, x):
    return 8 >= y >=0 and 8 >= x >=0

def change_pos(y, x):
    x += 1
    if x == 9:
        x = 0
        y += 1
    return y, x

def check_height_width(y1, x1, y2, x2, num1, num2):
    for i in range(9):
        if x1 != i:
            if table[y1][i] == num1:
                return True
        if y1 != i:
            if table[i][x1] == num1:
                return True
        
        if x2 != i:
            if table[y2][i] == num2:
                return True
        if y2 != i:
            if table[i][x2] == num2:
                return True
    return False

def check_cross(y, x, num):
    for i in range((y // 3) * 3, (y // 3) * 3 + 3):
        for j in range((x // 3) * 3, (x // 3) * 3 + 3):
            if table[i][j] == num and i != y and j != x:
                return True
            
    return False

def check(y1, x1, y2, x2, num1, num2):
    if check_height_width(y1, x1, y2, x2, num1, num2):
        return False
    
    if check_cross(y1, x1, num1) or check_cross(y2, x2, num2):
        return False
        
    return True

def solve(i,j, visited):
    global cnt
    if i == 8 and j == 8:
        print("Puzzle", cnt)
        for i in range(9):
            for j in range(9):
                print(table[i][j], end='')
            print()
        return True
    
    if table[i][j] != 0:
        new_i, new_j = change_pos(i, j)
        return solve(new_i, new_j, visited)
    
    
    for dy, dx in [(0, 1), (1, 0)]: # 세로로 넣어보기, 가로로 넣어보기
        ny, nx = i + dy, j + dx
        if not is_range(ny, nx) or table[ny][nx] != 0:
            continue
        
        for num1 in range(1, 10):
            for num2 in range(1, 10):
                if not visited[num1][num2] and num1 != num2:
                    if check(i, j, ny, nx, num1, num2):
                        visited[num1][num2] = True
                        visited[num2][num1] = True
                        table[i][j] = num1
                        table[ny][nx] = num2
                        
                        new_i, new_j = change_pos(i, j)
                        if solve(new_i, new_j, visited):
                            return True
                        
                        table[i][j] = 0
                        table[ny][nx] = 0
                        visited[num1][num2] = False
                        visited[num2][num1] = False

cnt = 1
while True:
    N = int(input().strip())
    table = [[0 for _ in range(9)] for _ in range(9)]
    visited = [[False for _ in range(10)] for _ in range(10)]
    if N == 0:
        break
    
    for _ in range(N):
        U, LU, V, LV = map(str, input().split())
        num1 = int(U)
        y1, x1 = get_pos(LU)
        num2 = int(V)
        y2, x2 = get_pos(LV)
        table[y1][x1] = num1
        table[y2][x2] = num2
        visited[num1][num2] = True
        visited[num2][num1] = True
    
    for num, pos in enumerate(list(map(str, input().split()))):
        y, x = get_pos(pos)
        table[y][x] = num+1
    
    solve(0, 0, visited)
    cnt += 1

🎯 피드백 및 개선사항

개인적으로 복잡한 문제나 이러한 조건이 많은 분기의 문제를 풀때에는 여러함수를 나누어서 나중에 어딘가에 문제가 생겨도 디버깅이 쉽고 문제를 빠르게 수정할 수 있어서 최근에 작고 많은 함수로 쪼개는 연습을 하고 있습니다.