[BOJ] 15686๋ฒ: ์นํจ ๋ฐฐ๋ฌ
๋ฌธ์ ํฌ๊ธฐ๊ฐ N×N์ธ ๋์๊ฐ ์๋ค. ๋์๋ 1×1ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๋์์ ๊ฐ ์นธ์ ๋น ์นธ, ์นํจ์ง, ์ง ์ค ํ๋์ด๋ค. ๋์์ ์นธ์ (r, c)์ ๊ฐ์ ํํ๋ก ๋ํ๋ด๊ณ , rํ c์ด ๋๋ ์์์๋ถํฐ r๋ฒ์งธ ์นธ, ์ผ์ชฝ์์๋ถํฐ c๋ฒ์งธ ์นธ์ ์๋ฏธํ๋ค. r๊ณผ c๋ 1๋ถํฐ ์์ํ๋ค. ์ด ๋์์ ์ฌ๋ ์ฌ๋๋ค์ ์นํจ์ ๋งค์ฐ ์ข์ํ๋ค. ๋ฐ๋ผ์, ์ฌ๋๋ค์ "์นํจ ๊ฑฐ๋ฆฌ"๋ผ๋ ๋ง์ ์ฃผ๋ก ์ฌ์ฉํ๋ค. ์นํจ ๊ฑฐ๋ฆฌ๋ ์ง๊ณผ ๊ฐ์ฅ ๊ฐ๊น์ด ์นํจ์ง ์ฌ์ด์ ๊ฑฐ๋ฆฌ์ด๋ค. ์ฆ, ์นํจ ๊ฑฐ๋ฆฌ๋ ์ง์ ๊ธฐ์ค์ผ๋ก ์ ํด์ง๋ฉฐ, ๊ฐ๊ฐ์ ์ง์ ์นํจ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ๋์์ ์นํจ ๊ฑฐ๋ฆฌ๋ ๋ชจ๋ ์ง์ ์นํจ ๊ฑฐ๋ฆฌ์ ํฉ์ด๋ค. ์์์ ๋ ์นธ (r1, c1)๊ณผ (r2, c2) ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ |r1-r2| + |c1-c2|๋ก ๊ตฌํ๋ค. ์๋ฅผ ๋ค์ด, ์๋์ ๊ฐ์ ์ง..
2024. 1. 16.