๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก์Šค๋„์ฟ  (1)

JUINTINATION

๋ฐฑ์ค€ 2580๋ฒˆ: ์Šค๋„์ฟ 

๋ฌธ์ œ https://www.acmicpc.net/problem/2580 2580๋ฒˆ: ์Šค๋„์ฟ  ์Šค๋„์ฟ ๋Š” 18์„ธ๊ธฐ ์Šค์œ„์Šค ์ˆ˜ํ•™์ž๊ฐ€ ๋งŒ๋“  '๋ผํ‹ด ์‚ฌ๊ฐํ˜•'์ด๋ž‘ ํผ์ฆ์—์„œ ์œ ๋ž˜ํ•œ ๊ฒƒ์œผ๋กœ ํ˜„์žฌ ๋งŽ์€ ์ธ๊ธฐ๋ฅผ ๋ˆ„๋ฆฌ๊ณ  ์žˆ๋‹ค. ์ด ๊ฒŒ์ž„์€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ๊ฐ€๋กœ, ์„ธ๋กœ ๊ฐ๊ฐ 9๊ฐœ์”ฉ ์ด 81๊ฐœ์˜ ์ž‘์€ ์นธ์œผ๋กœ ์ด๋ฃจ www.acmicpc.net ํ’€์ด ์Šค๋„์ฟ  ๊ทœ์น™์— ๋งž์ถฐ 9 x 9 ํฌ๊ธฐ์˜ ๋ณด๋“œ๋ฅผ ์ฑ„์šฐ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. dfs๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ชจ๋“  ์นธ์— ๋Œ€ํ•ด ์–ด๋–ค ์ˆซ์ž๊ฐ€ ํ•ด๋‹น ์นธ์— ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋Š”์ง€์— ๋Œ€ํ•œ ์—ฌ๋ถ€๋ฅผ sudoku ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ํ™•์ธ๋ฐ›์•„๊ฐ€๋ฉฐ 2์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด์— ๊ธฐ๋กํ•˜๋Š” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ–ˆ์Šต๋‹ˆ๋‹ค. ์ฝ”๋“œ C์–ธ์–ด 2์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด arr๋กœ 9 x 9 ํฌ๊ธฐ์˜ ๋ณด๋“œ๋ฅผ ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค. dfs ํ•จ์ˆ˜์—์„œ ๋ณด๋“œ์˜ (x, y)์˜ ์œ„์น˜์— ์žˆ๋Š” ์ˆซ์ž๋ฅผ arr[y][..