[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋ธ”๋ก ์ด๋™ํ•˜๊ธฐ :: c++, ์ฝ”๋“œ, DFS ์“ฐ๋ฉด ์•ˆ๋˜๋Š” ์ด์œ , BFS
Algorithm ๋ฌธ์ œ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค 2021. 1. 17. 23:09

๋ธ”๋ก ์ด๋™ํ•˜๊ธฐ โ˜…โ˜…โ˜…โ˜†โ˜† LEVEL 3 ๋ฌธ์ œ ๋ธ”๋ก ์ด๋™ํ•˜๊ธฐ ๋ฌธ์ œ ๋งํฌ ๋ฌธ์ œ ์„ค๋ช… ๋กœ๋ด‡๊ฐœ๋ฐœ์ž ๋ฌด์ง€๋Š” ํ•œ ๋‹ฌ ์•ž์œผ๋กœ ๋‹ค๊ฐ€์˜จ ์นด์นด์˜ค๋ฐฐ ๋กœ๋ด‡๊ฒฝ์ง„๋Œ€ํšŒ์— ์ถœํ’ˆํ•  ๋กœ๋ด‡์„ ์ค€๋น„ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์ค€๋น„ ์ค‘์ธ ๋กœ๋ด‡์€ 2 x 1 ํฌ๊ธฐ์˜ ๋กœ๋ด‡์œผ๋กœ ๋ฌด์ง€๋Š” 0๊ณผ 1๋กœ ์ด๋ฃจ์–ด์ง„ N x N ํฌ๊ธฐ์˜ ์ง€๋„์—์„œ 2 x 1 ํฌ๊ธฐ์ธ ๋กœ๋ด‡์„ ์›€์ง์—ฌ (N, N) ์œ„์น˜๊นŒ์ง€ ์ด๋™ ํ•  ์ˆ˜ ์žˆ๋„๋ก ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋กœ๋ด‡์ด ์ด๋™ํ•˜๋Š” ์ง€๋„๋Š” ๊ฐ€์žฅ ์™ผ์ชฝ, ์ƒ๋‹จ์˜ ์ขŒํ‘œ๋ฅผ (1, 1)๋กœ ํ•˜๋ฉฐ ์ง€๋„ ๋‚ด์— ํ‘œ์‹œ๋œ ์ˆซ์ž 0์€ ๋นˆ์นธ์„ 1์€ ๋ฒฝ์„ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค. ๋กœ๋ด‡์€ ๋ฒฝ์ด ์žˆ๋Š” ์นธ ๋˜๋Š” ์ง€๋„ ๋ฐ–์œผ๋กœ๋Š” ์ด๋™ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๋กœ๋ด‡์€ ์ฒ˜์Œ์— ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ขŒํ‘œ (1, 1) ์œ„์น˜์—์„œ ๊ฐ€๋กœ๋ฐฉํ–ฅ์œผ๋กœ ๋†“์—ฌ์žˆ๋Š” ์ƒํƒœ๋กœ ์‹œ์ž‘ํ•˜๋ฉฐ, ์•ž๋’ค ๊ตฌ๋ถ„์—†์ด ์›€์ง์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋กœ๋ด‡์ด ์›€..