문제 링크입니다: https://www.acmicpc.net/problem/4574
4574번: 스도미노쿠
문제 스도쿠가 세계적으로 유행이 된 이후에, 비슷한 퍼즐이 매우 많이 나왔다. 게임 매거진 2009년 7월호에는 스도쿠와 도미노를 혼합한 게임인 스도미노쿠가 소개되었다. 이 퍼즐은 스도쿠 규칙을 따른다. 스도쿠는 9×9 크기의 그리드를 1부터 9까지 숫자를 이용해서 채워야 한다. 스도쿠는 다음과 같은 조건을 만족하게 숫자를 채워야 한다. 각 행에는 1부터 9까지 숫자가 하나씩 있어야 한다. 각 열에는 1부터 9까지 숫자가 하나씩 있어야 한다. 3×3크기
www.acmicpc.net
스도쿠 문제인데 칸 하나하나에 숫자를 넣는 대신 2 * 1 혹은 1 * 2 도미노를 넣어야하는 복잡한 문제였습니다.
우선, 이 문제를 풀기 위해서는 스도쿠 개념을 알아야합니다.
1. 각 행에 1 ~ 9가 각각 하나씩 나와야합니다.
2. 각 열에 1 ~ 9가 각각 하나씩 나와야합니다.
3. 3 * 3 정사각형 안에 1 ~ 9가 각각 하나씩 나와야합니다.
스도쿠 판에 있는 숫자를 표시하기 위해 sudoku 배열을 이용하였고,
행, 열, 3 * 3 정사각형 안에 있는 숫자를 파악하기 위해 row, col, square 배열을 이용했습니다.
정답이 여러개가 나올 수 있기 때문에 하나만 출력하기 위해 flag를 이용하였습니다.
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 15361번 Izbori (5) | 2019.05.03 |
|---|---|
| 백준 15360번 Rasvjeta (2) | 2019.05.03 |
| 백준 3568번 iSharp (0) | 2019.05.02 |
| 백준 2290번 LCD Test (0) | 2019.05.02 |
| 백준 3190번 뱀 (5) | 2019.05.01 |