[백준 - C#] 1553번 도미노 찾기

문제링크

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

1553번: 도미노 찾기

 

문제

도미노의 크기는 1×2이고, 크기가 1×1인 칸으로 나누어져 있다. 칸은 수를 나타내며, 위와 같이 총 28가지가 있다.

크기가 8×7인 격자가 있고, 격자의 각 칸에는 정수가 하나씩 들어있다.
위의 도미노를 이용해 문제의 격자와 같은 상태를 만드는 방법의 수를 구해보자.

격자의 칸에 적힌 수는 도미노의 칸이 의미하는 수와 같아야 한다.
도미노는 회전할 수 있으며, 같은 도미노를 여러 번 사용하면 안된다.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

총 8개의 줄에 격자의 상태가 주어진다. 격자에는 0부터 6까지의 수만 존재한다.

출력

첫째 줄에 경우의 수를 출력한다.

 

문제정리

1. 도미노의 값은 총 두가지로 구성되어 있고 28가지의 종류가 있습니다.
2. 격자의 크기는 8x7 로 총 56개 입니다.
3. 격자에는 0부터 6까지의 수가 존재합니다.
4. 가지고 있는 도미노로 격자를 채울 수 있는 모든 경우의 수를 구해야합니다.

이번 문제의 경우 주어진 도미노로 모든 격자를 채울 수 있는 경우의 수를 구해야하는 문제입니다.

도미노의 경우 가로와 세로로 놓을 수 있으며 주어진 문제는 백트래킹을 이용하여 풀라고 하여 완전탐색을 이용하여 풀이를 진행하였습니다.

 

 

int[,] grid = new int[8, 7];
 
// 격자 8*7 총 56개 입력
for (int i = 0; i < 8; i++)
{
    char[] input = reader.ReadLine().ToCharArray();
 
    for (int j = 0; j < 7; j++)
    {
        grid[i, j] = int.Parse(input[j].ToString());
    }
}
 
bool[,] visited = new bool[8, 7]; // 방문 했는 지 검사하는 변수
bool[,] domino = new bool[7, 7]; // 사용 한 도미노 인지 검사하는 변수

grid라는 변수에 모든 격자의 수를 입력 받고 visited와 domino 변수를 선언하였습니다.

visited의 경우 격자와 똑같은 크기로 해당 격자를 사용하였는지 체크하기 위해 선언한 변수이고 domino의 경우 7*7으로 사용한 도미노의 번호를 파악하기 위해 선언한 변수입니다.

 

Search 함수를 재귀로 돌며 완전탐색을 진행할 예정으로 아래의 코드는 함수 내부에 선언된 구문입니다.

 

if (x == 8) // 완전탐색이 끝났을 때 경우의 수 한개 추가
        return 1;
 
 int count = 0;
 int nextX = x; // 다음 탐색할 값
 int nextY = y + 1; // 다음 탐색할 값
 
 if (nextY == 7) // 열의 끝 (오른쪽) 도착 다음 행으로 이동
 {
   nextX = x + 1;
   nextY = 0;
}

x의 값이 8일 때 리턴 1을 해줍니다. 그 이유는 완전탐색이 모두 끝난 시점 즉 모든 도미노를 사용하여 격자를 채웠을 때는 x의 값이 8이 되었을 때 이므로 카운팅을 하나 추가합니다.

next에는 다음 탐색 값을 초기화 해주고 nextY의 값이 7이라면 열의 끝 쯕 오른쪽 끝에 도달한 것이므로 다음 행으로 이동하였습니다.

 

다음으로는 방문 하지 않았을 때랑 방문하였을 때 처리하는 구문입니다.

if (!visited[x, y]) // 방문하지 않았으면
{
    int current = grid[x, y]; // 현재 방문한 격자 값 ( 첫번째 값 )
    visited[x, y] = true;
    foreach (var (dx, dy) in d) // 방문한 값을 기준으로 오른쪽, 아래 검사 ( 두번째 값 )
    {
        int moveX = x + dx;
        int moveY = y + dy;
        if (moveX < 8 && moveY < 7) // 두번 째 값이 격자를 벗어나지 않는다면
        {
            int pair = grid[moveX, moveY]; // 두번 째 값
                                           // 두번째 값이 방문하지 않았고, 첫번째 값과 두번째 값이 사용하지 않았으면
            if (!visited[moveX, moveY] && !domino[current, pair])
            {
                // 도미노 두개 사용했다고 표기 (3,0) / (0,3)은 같은거기 때문
                domino[current, pair] = true;
                domino[pair, current] = true;
                visited[moveX, moveY] = true;
                // 다음 위치로 이동
                count += Search(nextX, nextY);
                // 백트래킹을 위하여 초기화
                visited[moveX, moveY] = false;
                domino[current, pair] = false;
                domino[pair, current] = false;
            }
        }
    }
    // 백트래킹을 위하여 초기화
    visited[x, y] = false;
    return count;
}
else
{
    // 방문했으면 다음 것으로 이동
    return Search(nextX, nextY);
}

dx와 dy를 이용하여 방문한 격자값에서 오른쪽과 아래쪽 값을 탐색합니다.

move는 dx dy를 이용하여 방문한 격자 값이며 해당 값을 방문하지 않았고 도미노의 값이 사용되지 않았으면

도미노의 값을 사용하고 방문했다고 표기 후 다음 값으로 이동하여 탐색을 진행합니다.

 

만약 방문 하였다면 바로 다음값으로 탐색을 속행하도록 하면 됩니다.

 

나머지는 전체코드를 보며 쭈욱 이해하시면 될 것 같습니다 .

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    (int, int)[] d = new (int, int)[2] { (0, 1), (1, 0) };
    int[,] grid = new int[8, 7];
 
    // 격자 8*7 총 56개 입력
    for (int i = 0; i < 8; i++)
    {
        char[] input = reader.ReadLine().ToCharArray();
 
        for (int j = 0; j < 7; j++)
        {
            grid[i, j] = int.Parse(input[j].ToString());
        }
    }
 
    bool[,] visited = new bool[8, 7]; // 방문 했는 지 검사하는 변수
    bool[,] domino = new bool[7, 7]; // 사용 한 도미노 인지 검사하는 변수
 
    writer.WriteLine(Search(0, 0));
 
    writer.Close();
    reader.Close();
 
    int Search(int x, int y)
    {
        if (x == 8) // 완전탐색이 끝났을 때 경우의 수 한개 추가
            return 1;
 
        int count = 0;
        int nextX = x; // 다음 탐색할 값
        int nextY = y + 1; // 다음 탐색할 값
 
        if (nextY == 7) // 열의 끝 (오른쪽) 도착 다음 행으로 이동
        {
            nextX = x + 1;
            nextY = 0;
        }
 
        if (!visited[x, y]) // 방문하지 않았으면
        {
            int current = grid[x, y]; // 현재 방문한 격자 값 ( 첫번째 값 )
            visited[x, y] = true;
 
            foreach (var (dx, dy) in d) // 방문한 값을 기준으로 오른쪽, 아래 검사 ( 두번째 값 )
            {
                int moveX = x + dx;
                int moveY = y + dy;
 
                if (moveX < 8 && moveY < 7) // 두번 째 값이 격자를 벗어나지 않는다면
                {
                    int pair = grid[moveX, moveY]; // 두번 째 값
 
                    // 두번째 값이 방문하지 않았고, 첫번째 값과 두번째 값이 사용하지 않았으면
                    if (!visited[moveX, moveY] && !domino[current, pair])
                    {
                        // 도미노 두개 사용했다고 표기 (3,0) / (0,3)은 같은거기 때문
                        domino[current, pair] = true;
                        domino[pair, current] = true;
 
                        visited[moveX, moveY] = true;
 
                        // 다음 위치로 이동
                        count += Search(nextX, nextY);
 
                        // 백트래킹을 위하여 초기화
                        visited[moveX, moveY] = false;
                        domino[current, pair] = false;
                        domino[pair, current] = false;
                    }
                }
            }
 
            // 백트래킹을 위하여 초기화
            visited[x, y] = false;
            return count;
        }
        else
        {
            // 방문했으면 다음 것으로 이동
            return Search(nextX, nextY);
        }
    }
}

 

참고 사이트 

https://latte-is-horse.tistory.com/331

[solved.ac 실버1] 1553_도미노 찾기 (파이썬, 백트래킹)

정말 설명을 친절하게 해주셔서 백트래킹에 대해 자세히 공부할 수 있었습니다.

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.