๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
CS/์•Œ๊ณ ๋ฆฌ์ฆ˜

[๋ฐฑ์ค€ 1012 ์œ ๊ธฐ๋† ๋ฐฐ์ถ”] ํŒŒ์ด์ฌ BFS ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ํ’€์ด

by ๐ŸŒปโ™š 2020. 9. 28.

์œ ๊ธฐ๋† ๋ฐฐ์ถ” ๋ฌธ์ œ

 

1012๋ฒˆ: ์œ ๊ธฐ๋† ๋ฐฐ์ถ”

์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— ๏ฟฝ

www.acmicpc.net

2์ฐจ์› ๋ฐฐ์—ด์˜ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฐญ์ด ์ฃผ์–ด์ง€๊ณ  0(๋•…) ๊ณผ 1(๋ฐฐ์ถ” ์‹ฌ์–ด์ ธ ์žˆ๋Š” ๋•…)๋กœ ๋ฐ์ดํ„ฐ๊ฐ€ ๊ตฌ๋ถ„๋ฉ๋‹ˆ๋‹ค. ๋ฐฐ์ถ”ํฐ ์ง€๋ ์ด๋ฅผ ๋ฐฐ์ถ”์— ์„œ์‹ํ•˜๊ฒŒ ํ•˜๋ฉด ์‚ฌ๋ฐฉ๋ฉด์œผ๋กœ ์ด๋™์ด ๊ฐ€๋Šฅํ•˜์—ฌ ๋‹ค๋ฅธ ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธ๊ฐ€ ๊ฐ€๋Šฅํ•˜๋‹ค. ํ•„์š”ํ•œ ๋ฐฐ์ถ”ํฐ ์ง€๋ ์ด์˜ ๋งˆ๋ฆฌ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ž…๋ ฅ ๋ฐ›๋Š” ์ •๋ณด๋กœ ์•„๋ž˜์™€ ๊ฐ™์ด ๋ฐฐ์ถ” ๋ฐญ์„ 2์ฐจ์› ๋ฐฐ์—ด ํ˜•ํƒœ๋กœ ๋งŒ๋“ค์–ด ์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

 

๋ฌธ์ œ ํ’€์ด

4๋ฐฉ๋ฉด์œผ๋กœ ์ด๋™์ด ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ ๊ฐ ์˜์—ญ๋‹น ํ•œ๋งˆ๋ฆฌ์˜ ๋ฐฐ์ถ”ํฐ ์ง€๋ ์ด๋ฅผ ๋ฐฐ์น˜ํ•˜๋ฉด ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ฆ‰, 1๋กœ๋˜์–ด์žˆ๋Š” ์˜์—ญ์ด ๋ช‡๊ฐœ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋ฏ€๋กœ BFS ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์„ ํ†ตํ•ด ํ’€์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

1. ์ž…๋ ฅ๋ฐ›์€ ์ง€๋ ์ด์˜ ์ขŒํ‘œ๋ฅผ 2์ฐจ์› ๋ฐฐ์—ด์— 1๋กœ ํ‘œ์‹œ
2. BFS ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์œผ๋กœ 1์˜ ์˜์—ญ์ด ๋ช‡๊ฐœ ์žˆ๋Š”์ง€ ํ™•์ธ

 

2์ฐจ์› ๋ฐฐ์—ด์˜ ๋†’์ด H, ๋„ˆ๋น„ W๋ผ๊ณ  ํ–ˆ์„๋•Œ ์ตœ์„ , ์ตœ์•… ๋ชจ๋‘ ์‹œ๊ฐ„ ๋ณต์žก๋„ O(HW)๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ๋ฐฉ๋ฌธ ์ •๋ณด๋ฅผ ๋‚จ๊ฒจ ๋ฐฉ๋ฌธ ์•ˆํ•œ ๊ณณ๋งŒ ์ˆœํšŒํ•˜์—ฌ 2์ฐจ์›๋ฐฐ์—ด ์ „์ฒด๋ฅผ ๋”ฑ ํ•œ๋ฒˆ๋งŒ ํ™•์ธํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

 

ํŒŒ์ด์ฌ ์ฝ”๋“œ

๋Œ“๊ธ€