๋์ด๋: ๊ณจ๋ 4 ํ์ด ์๊ณ ๋ฆฌ์ฆ: BFS ๋ฌธ์ N×Nํฌ๊ธฐ์ ๋ ์ด ์๊ณ , ๋ ์ 1×1๊ฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ฐ๊ฐ์ ๋ ์๋ ๋๋ผ๊ฐ ํ๋์ฉ ์กด์ฌํ๋ฉฐ, rํ c์ด์ ์๋ ๋๋ผ์๋ A[r][c]๋ช ์ด ์ด๊ณ ์๋ค. ์ธ์ ํ ๋๋ผ ์ฌ์ด์๋ ๊ตญ๊ฒฝ์ ์ด ์กด์ฌํ๋ค. ๋ชจ๋ ๋๋ผ๋ 1×1 ํฌ๊ธฐ์ด๊ธฐ ๋๋ฌธ์, ๋ชจ๋ ๊ตญ๊ฒฝ์ ์ ์ ์ฌ๊ฐํ ํํ์ด๋ค. ์ค๋๋ถํฐ ์ธ๊ตฌ ์ด๋์ด ์์๋๋ ๋ ์ด๋ค. ์ธ๊ตฌ ์ด๋์ ํ๋ฃจ ๋์ ๋ค์๊ณผ ๊ฐ์ด ์งํ๋๊ณ , ๋ ์ด์ ์๋ ๋ฐฉ๋ฒ์ ์ํด ์ธ๊ตฌ ์ด๋์ด ์์ ๋๊น์ง ์ง์๋๋ค. ๊ตญ๊ฒฝ์ ์ ๊ณต์ ํ๋ ๋ ๋๋ผ์ ์ธ๊ตฌ ์ฐจ์ด๊ฐ L๋ช ์ด์, R๋ช ์ดํ๋ผ๋ฉด, ๋ ๋๋ผ๊ฐ ๊ณต์ ํ๋ ๊ตญ๊ฒฝ์ ์ ์ค๋ ํ๋ฃจ ๋์ ์ฐ๋ค. ์์ ์กฐ๊ฑด์ ์ํด ์ด์ด์ผํ๋ ๊ตญ๊ฒฝ์ ์ด ๋ชจ๋ ์ด๋ ธ๋ค๋ฉด, ์ธ๊ตฌ ์ด๋์ ์์ํ๋ค. ๊ตญ๊ฒฝ์ ์ด ์ด๋ ค์์ด ์ธ์ ํ ์นธ๋ง์ ์ด์ฉํด ์ด๋ํ ..
๋์ด๋: ๊ณจ๋ 3 ํ์ด ์๊ณ ๋ฆฌ์ฆ: BFS ๋ฌธ์ N×M์ ๋ชจ๋์ข ์ด ์์ ์์ฃผ ์์ ์น์ฆ๊ฐ ๊ณผ ๊ฐ์ด ํ์๋์ด ์๋ค. ๋จ, N ์ ์ธ๋ก ๊ฒฉ์์ ์์ด๊ณ , M ์ ๊ฐ๋ก ๊ฒฉ์์ ์์ด๋ค. ์ด ์น์ฆ๋ ๋๋ ๋ณด๊ด์ ํด์ผ๋ง ํ๋๋ฐ ์ค๋ด์จ๋์ ๋ด์ด๋์ผ๋ฉด ๊ณต๊ธฐ์ ์ ์ดํ์ฌ ์ฒ์ฒํ ๋ น๋๋ค. ๊ทธ๋ฐ๋ฐ ์ด๋ฌํ ๋ชจ๋์ข ์ด ๋ชจ์์ ์น์ฆ์์ ๊ฐ ์น์ฆ ๊ฒฉ์(์ ์ ์ ์ฌ๊ฐํ ๋ชจ์)์ 4๋ณ ์ค์์ ์ ์ด๋ 2๋ณ ์ด์์ด ์ค๋ด์จ๋์ ๊ณต๊ธฐ์ ์ ์ดํ ๊ฒ์ ์ ํํ ํ์๊ฐ๋ง์ ๋ น์ ์์ด์ ธ ๋ฒ๋ฆฐ๋ค. ๋ฐ๋ผ์ ์๋ ๋ชจ์๊ณผ ๊ฐ์ ์น์ฆ(ํ์์ผ๋ก ํ์๋ ๋ถ๋ถ)๋ผ๋ฉด C๋ก ํ์๋ ๋ชจ๋ ์น์ฆ ๊ฒฉ์๋ ํ ์๊ฐ ํ์ ์ฌ๋ผ์ง๋ค. ์ ๊ฐ์ด ์น์ฆ ๋ด๋ถ์ ์๋ ๊ณต๊ฐ์ ์น์ฆ ์ธ๋ถ ๊ณต๊ธฐ์ ์ ์ดํ์ง ์๋ ๊ฒ์ผ๋ก ๊ฐ์ ํ๋ค. ๊ทธ๋ฌ๋ฏ ๋ก ์ด ๊ณต๊ฐ์ ์ ์ดํ ์น์ฆ ๊ฒฉ์๋ ๋ น์ง ์๊ณ C๋ก ํ์๋ ์น์ฆ..
๋์ด๋: ๊ณจ๋ 2 ํ์ด ์๊ณ ๋ฆฌ์ฆ: BFS ๋ฌธ์ ์์ฃผ ๋จผ ๋ฏธ๋์ ์ฌ๋๋ค์ด ๊ฐ์ฅ ๋ง์ด ์ฌ์ฉํ๋ ๋์ค๊ตํต์ ํ์ดํผํ๋ธ์ด๋ค. ํ์ดํผํ๋ธ ํ๋๋ ์ญ K๊ฐ๋ฅผ ์๋ก ์ฐ๊ฒฐํ๋ค. 1๋ฒ์ญ์์ N๋ฒ์ญ์ผ๋ก ๊ฐ๋๋ฐ ๋ฐฉ๋ฌธํ๋ ์ต์ ์ญ์ ์๋ ๋ช ๊ฐ์ผ๊น? ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ญ์ ์ N๊ณผ ํ ํ์ดํผํ๋ธ๊ฐ ์๋ก ์ฐ๊ฒฐํ๋ ์ญ์ ๊ฐ์ K, ํ์ดํผํ๋ธ์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) ๋ค์ M๊ฐ ์ค์๋ ํ์ดํผํ๋ธ์ ์ ๋ณด๊ฐ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ด K๊ฐ ์ซ์๊ฐ ์ฃผ์ด์ง๋ฉฐ, ์ด ์ซ์๋ ๊ทธ ํ์ดํผํ๋ธ๊ฐ ์๋ก ์ฐ๊ฒฐํ๋ ์ญ์ ๋ฒํธ์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ 1๋ฒ์ญ์์ N๋ฒ์ญ์ผ๋ก ๊ฐ๋๋ฐ ๋ฐฉ๋ฌธํ๋ ์ญ์ ๊ฐ์์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ, ๊ฐ ์ ์๋ค๋ฉด -1์ ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ 1 9 3 5 1 2 3 ..
๋ฌธ์ NxN ํฌ๊ธฐ์ ์ํ๊ด์ด ์๋ค. ์ํ๊ด์ 1x1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ง๋ฉฐ, ํน์ ํ ์์น์๋ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ ์ ์๋ค. ๋ชจ๋ ๋ฐ์ด๋ฌ์ค๋ 1๋ฒ๋ถํฐ K๋ฒ๊น์ง์ ๋ฐ์ด๋ฌ์ค ์ข ๋ฅ ์ค ํ๋์ ์ํ๋ค. ์ํ๊ด์ ์กด์ฌํ๋ ๋ชจ๋ ๋ฐ์ด๋ฌ์ค๋ 1์ด๋ง๋ค ์, ํ, ์ข, ์ฐ์ ๋ฐฉํฅ์ผ๋ก ์ฆ์ํด ๋๊ฐ๋ค. ๋จ, ๋งค ์ด๋ง๋ค ๋ฒํธ๊ฐ ๋ฎ์ ์ข ๋ฅ์ ๋ฐ์ด๋ฌ์ค๋ถํฐ ๋จผ์ ์ฆ์ํ๋ค. ๋ํ ์ฆ์ ๊ณผ์ ์์ ํน์ ํ ์นธ์ ์ด๋ฏธ ์ด๋ ํ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ๋ค๋ฉด, ๊ทธ ๊ณณ์๋ ๋ค๋ฅธ ๋ฐ์ด๋ฌ์ค๊ฐ ๋ค์ด๊ฐ ์ ์๋ค. ์ํ๊ด์ ํฌ๊ธฐ์ ๋ฐ์ด๋ฌ์ค์ ์์น ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, S์ด๊ฐ ์ง๋ ํ์ (X,Y)์ ์กด์ฌํ๋ ๋ฐ์ด๋ฌ์ค์ ์ข ๋ฅ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ง์ฝ S์ด๊ฐ ์ง๋ ํ์ ํด๋น ์์น์ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ์ง ์๋๋ค๋ฉด, 0์ ์ถ๋ ฅํ๋ค. ์ด ๋ X์ Y๋ ๊ฐ๊ฐ ํ๊ณผ..
๋ฌธ์ ๐ https://www.acmicpc.net/problem/2468 2468๋ฒ: ์์ ์์ญ ์ฌ๋๋ฐฉ์ฌ์ฒญ์์๋ ๋ง์ ๋น๊ฐ ๋ด๋ฆฌ๋ ์ฅ๋ง์ฒ ์ ๋๋นํด์ ๋ค์๊ณผ ๊ฐ์ ์ผ์ ๊ณํํ๊ณ ์๋ค. ๋จผ์ ์ด๋ค ์ง์ญ์ ๋์ด ์ ๋ณด๋ฅผ ํ์ ํ๋ค. ๊ทธ ๋ค์์ ๊ทธ ์ง์ญ์ ๋ง์ ๋น๊ฐ ๋ด๋ ธ์ ๋ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ www.acmicpc.net ํ์ด ์๊ณ ๋ฆฌ์ฆ: DFS ๋์ด๋: ์ค๋ฒ 1 ์ ๊ทผ ๋ฐฉ๋ฒ โ ๋๋ DFS๋ก ๋ฌธ์ ๋ฅผ ํ์ดํ๋ค. ๋ฌธ์ ๊ฐ ์๊ตฌํ๋ ๊ฒ์ ์กฐ๊ฑด์ ๋ง๋ ์ฐ๊ฒฐ ์์๊ฐ ๋ช ๊ฐ์ธ์ง ์ฐพ๋ ๊ฒ์ด๋ค. ๋น๋ฌผ์ ์ ๊ธฐ์ง ์๋ ๋์ด์ ์ฐ๊ฒฐ์์๋ฅผ ์ฐพ๊ธฐ ๋๋ฌธ์ ๋น๊ฐ ๋ด๋ ธ์ ๋ ์์ด๋ ๋์ด๋ณด๋ค ๋์ ์์๋ค์ ์ฐพ์์ฃผ๋ฉด ๋๋ค. ์ฃผ์ ์ฌํญ์ผ๋ก "์๋ฌด ์ง์ญ๋ ๋ฌผ์ ์ ๊ธฐ์ง ์์ ์๋ ์๋ค."๋ผ๋ ๋ง์ด ์๊ธฐ ๋๋ฌธ์ ๋น๊ฐ ์ ๋ด๋ ค์ ๋ชจ๋ ์ ์ ๊ธฐ๋ ์ํฉ๋ ์์..
๋ฌธ์ ์ฐจ์ธ๋ ์๋์ธ ํ๋๋ ๊ฐ์๋ ๊ณ ๋ญ์ง์์ ์ ๊ธฐ๋ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๊ธฐ๋ก ํ์๋ค. ๋์ฝ์ ์ฐ์ง ์๊ณ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๋ ค๋ฉด ๋ฐฐ์ถ๋ฅผ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธํ๋ ๊ฒ์ด ์ค์ํ๊ธฐ ๋๋ฌธ์, ํ๋๋ ํด์ถฉ ๋ฐฉ์ง์ ํจ๊ณผ์ ์ธ ๋ฐฐ์ถํฐ์ง๋ ์ด๋ฅผ ๊ตฌ์ ํ๊ธฐ๋ก ๊ฒฐ์ฌํ๋ค. ์ด ์ง๋ ์ด๋ ๋ฐฐ์ถ๊ทผ์ฒ์ ์์ํ๋ฉฐ ํด์ถฉ์ ์ก์ ๋จน์์ผ๋ก์จ ๋ฐฐ์ถ๋ฅผ ๋ณดํธํ๋ค. ํนํ, ์ด๋ค ๋ฐฐ์ถ์ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ ๋ง๋ฆฌ๋ผ๋ ์ด๊ณ ์์ผ๋ฉด ์ด ์ง๋ ์ด๋ ์ธ์ ํ ๋ค๋ฅธ ๋ฐฐ์ถ๋ก ์ด๋ํ ์ ์์ด, ๊ทธ ๋ฐฐ์ถ๋ค ์ญ์ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธ๋ฐ์ ์ ์๋ค. ํ ๋ฐฐ์ถ์ ์ํ์ข์ฐ ๋ค ๋ฐฉํฅ์ ๋ค๋ฅธ ๋ฐฐ์ถ๊ฐ ์์นํ ๊ฒฝ์ฐ์ ์๋ก ์ธ์ ํด์๋ ๊ฒ์ด๋ค. ํ๋๊ฐ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๋ ๋ ์ ๊ณ ๋ฅด์ง ๋ชปํด์ ๋ฐฐ์ถ๋ฅผ ๊ตฐ๋ฐ๊ตฐ๋ฐ ์ฌ์ด ๋์๋ค. ๋ฐฐ์ถ๋ค์ด ๋ชจ์ฌ์๋ ๊ณณ์๋ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ ๋ง๋ฆฌ๋ง ์์ผ๋ฉด ๋๋ฏ๋ก ์๋ก ์ธ์ ํด์๋ ๋ฐฐ์ถ๋ค์ด ๋ช ๊ตฐ..
๋ฌธ์ ์ธ๋ก R์นธ, ๊ฐ๋ก C์นธ์ผ๋ก ๋ ํ ๋ฌ์์ ๋ณด๋๊ฐ ์๋ค. ๋ณด๋์ ๊ฐ ์นธ์๋ ๋๋ฌธ์ ์ํ๋ฒณ์ด ํ๋์ฉ ์ ํ ์๊ณ , ์ข์ธก ์๋จ ์นธ (1ํ 1์ด) ์๋ ๋ง์ด ๋์ฌ์๋ค. ๋ง์ ์ํ์ข์ฐ๋ก ์ธ์ ํ ๋ค ์นธ ์ค์ ํ ์นธ์ผ๋ก ์ด๋ํ ์ ์๋๋ฐ, ์๋ก ์ด๋ํ ์นธ์ ์ ํ ์๋ ์ํ๋ฒณ์ ์ง๊ธ๊น์ง ์ง๋์จ ๋ชจ๋ ์นธ์ ์ ํ ์๋ ์ํ๋ฒณ๊ณผ๋ ๋ฌ๋ผ์ผ ํ๋ค. ์ฆ, ๊ฐ์ ์ํ๋ฒณ์ด ์ ํ ์นธ์ ๋ ๋ฒ ์ง๋ ์ ์๋ค. ์ข์ธก ์๋จ์์ ์์ํด์, ๋ง์ด ์ต๋ํ ๋ช ์นธ์ ์ง๋ ์ ์๋์ง๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ง์ด ์ง๋๋ ์นธ์ ์ข์ธก ์๋จ์ ์นธ๋ ํฌํจ๋๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ R๊ณผ C๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. (1 ≤ R,C ≤ 20) ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๋ง์ด ์ง๋ ์ ์๋ ์ต๋์ ์นธ ์๋ฅผ ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ 1 3 6 HFDFFB AJH..
๋ฌธ์ ๋ ์ผ ๋ก๋๋ {1, 2, ..., 49}์์ ์ 6๊ฐ๋ฅผ ๊ณ ๋ฅธ๋ค. ๋ก๋ ๋ฒํธ๋ฅผ ์ ํํ๋๋ฐ ์ฌ์ฉ๋๋ ๊ฐ์ฅ ์ ๋ช ํ ์ ๋ต์ 49๊ฐ์ง ์ ์ค k(k>6)๊ฐ์ ์๋ฅผ ๊ณจ๋ผ ์งํฉ S๋ฅผ ๋ง๋ ๋ค์ ๊ทธ ์๋ง ๊ฐ์ง๊ณ ๋ฒํธ๋ฅผ ์ ํํ๋ ๊ฒ์ด๋ค. ์๋ฅผ ๋ค์ด, k=8, S={1,2,3,5,8,13,21,34}์ธ ๊ฒฝ์ฐ ์ด ์งํฉ S์์ ์๋ฅผ ๊ณ ๋ฅผ ์ ์๋ ๊ฒฝ์ฐ์ ์๋ ์ด 28๊ฐ์ง์ด๋ค. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]) ์งํฉ S์ k๊ฐ ์ฃผ์ด์ก์ ๋, ์๋ฅผ ๊ณ ๋ฅด๋ ๋ชจ๋ ๋ฐฉ๋ฒ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ ๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์ฒซ ..
๋ฌธ์ ๋์์ด๋ ์งํ๊ตฌ๋ฆฌ ์๋ฆฌ์ฌ๋ก ๋ช ์ฑ์ ๋ ๋ ธ์๋ค. ์ด๋ฒ์๋ ์ด์ ์ ์์๋ ์๋ก์ด ์๋ฆฌ์ ๋์ ์ ํด๋ณด๋ ค๊ณ ํ๋ค. ์ง๊ธ ๋์์ด์ ์์๋ ์ฌ๋ฃ๊ฐ N๊ฐ ์๋ค. ๋์์ด๋ ๊ฐ ์ฌ๋ฃ์ ์ ๋ง S์ ์ด๋ง B๋ฅผ ์๊ณ ์๋ค. ์ฌ๋ฌ ์ฌ๋ฃ๋ฅผ ์ด์ฉํด์ ์๋ฆฌํ ๋, ๊ทธ ์์์ ์ ๋ง์ ์ฌ์ฉํ ์ฌ๋ฃ์ ์ ๋ง์ ๊ณฑ์ด๊ณ , ์ด๋ง์ ํฉ์ด๋ค. ์๊ฑฐ๋ ์ด ์์์ ์ข์ํ๋ ์ฌ๋์ ๋ง์ง ์๋ค. ๋์์ด๋ ์ฌ๋ฃ๋ฅผ ์ ์ ํ ์์ด์ ์๋ฆฌ์ ์ ๋ง๊ณผ ์ด๋ง์ ์ฐจ์ด๋ฅผ ์๊ฒ ๋ง๋ค๋ ค๊ณ ํ๋ค. ๋, ๋ฌผ์ ์๋ฆฌ๋ผ๊ณ ํ ์๋ ์๊ธฐ ๋๋ฌธ์, ์ฌ๋ฃ๋ ์ ์ด๋ ํ๋ ์ฌ์ฉํด์ผ ํ๋ค. ์ฌ๋ฃ์ ์ ๋ง๊ณผ ์ด๋ง์ด ์ฃผ์ด์ก์ ๋, ์ ๋ง๊ณผ ์ด๋ง์ ์ฐจ์ด๊ฐ ๊ฐ์ฅ ์์ ์๋ฆฌ๋ฅผ ๋ง๋๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ฌ๋ฃ์ ๊ฐ์ N(1 ≤ N ≤ 10)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ ์ค์๋ ๊ทธ ์ฌ๋ฃ์ ์ ..