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

[๋ฐฑ์ค€ 10026 ์ ๋ก์ƒ‰์•ฝ] ํŒŒ์ด์ฌ BFS ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ํ’€์ด

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

์ ๋ก์ƒ‰์•ฝ ๋ฌธ์ œ

 

10026๋ฒˆ: ์ ๋ก์ƒ‰์•ฝ

์ ๋ก์ƒ‰์•ฝ์€ ๋นจ๊ฐ„์ƒ‰๊ณผ ์ดˆ๋ก์ƒ‰์˜ ์ฐจ์ด๋ฅผ ๊ฑฐ์˜ ๋Š๋ผ์ง€ ๋ชปํ•œ๋‹ค. ๋”ฐ๋ผ์„œ, ์ ๋ก์ƒ‰์•ฝ์ธ ์‚ฌ๋žŒ์ด ๋ณด๋Š” ๊ทธ๋ฆผ์€ ์•„๋‹Œ ์‚ฌ๋žŒ์ด ๋ณด๋Š” ๊ทธ๋ฆผ๊ณผ๋Š” ์ข€ ๋‹ค๋ฅผ ์ˆ˜ ์žˆ๋‹ค. ํฌ๊ธฐ๊ฐ€ N×N์ธ ๊ทธ๋ฆฌ๋“œ์˜ ๊ฐ ์นธ์— R(๋นจ๊ฐ•), G(์ดˆ๋ก)

www.acmicpc.net

RGB 3๊ฐ€์ง€ ๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ง„ N * N ๋ณด๋“œํŒ์ด ์ฃผ์–ด์งˆ๋•Œ ์ผ๋ฐ˜์‚ฌ๋žŒ๊ณผ ์ ๋ก์ƒ‰์•ฝ์ธ ์‚ฌ๋žŒ์ด ๋ณด๋Š” ๊ตฌ์—ญ์˜ ์ˆ˜๋ฅผ ๊ฐ๊ฐ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ ๋ก์ƒ‰์•ฝ์€ R๊ณผ G๋ฅผ ํ•˜๋‚˜์˜ ์ƒ‰์œผ๋กœ ๋ณด์ž…๋‹ˆ๋‹ค. ์ฆ‰, ์•„๋ž˜์™€ ๊ฐ™์ด ๊ตฌ์—ญ์ด ๋‚˜๋‰˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

๋ฌธ์ œ ํ’€์ด

2์ฐจ์› ๋ฐฐ์—ด์˜ ์˜์—ญ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋กœ BFS ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด์„œ ํ’€๋ฉด ๋ ๊ฒƒ์œผ๋กœ ํŒ๋‹จํ–ˆ์Šต๋‹ˆ๋‹ค. ๋‹จ, 2๊ฐ€์ง€ ๊ฒฝ์šฐ๊ฐ€ ๋ฐœ์ƒํ•˜๊ธฐ ๋•Œ๋ฌธ์— 2๊ฐ€์ง€ ๋ฒ„์ „์˜ ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด์ฃผ๊ณ  ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ์‹์„ ์„ ํƒํ–ˆ์Šต๋‹ˆ๋‹ค. N์˜ ์ตœ๋Œ€ ๊ฐ’์ด 100์ด๋ฏ€๋กœ ๋ฐฐ์—ด์„ ํ•˜๋‚˜ ๋” ์ƒ์„ฑํ•˜๋Š”๋ฐ ํฌ๊ฒŒ ๋ฌด๋ฆฌ๊ฐ€ ์—†๋Š”๊ฒƒ์œผ๋กœ ํŒ๋‹จํ–ˆ์Šต๋‹ˆ๋‹ค.

 

1. ์ž…๋ ฅ ๋ฐ›์€ ๋ฐฐ์—ด๋กœ ์ ๋ก์ƒ‰์•ฝ์šฉ ๋ฐฐ์—ด ์ƒ์„ฑ --> R,G : 1      B : 2
2. ๊ฐ๊ฐ ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๊ฐ€ ๊ฐ™์œผ๋ฏ€๋กœ ๋™์‹œ์— BFS ์ˆœํšŒ 

 

2์ฐจ์› ๋ฐฐ์—ด์ด N * N ์ผ๋•Œ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(N^2)์œผ๋กœ ๊ณ„์‚ฐ ๋ฉ๋‹ˆ๋‹ค.

๋ฐฐ์—ด์˜ ๊ฐ๊ฐ ์œ„์น˜๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ์˜์—ญ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•˜๊ณ  ๋ฐฉ๋ฌธํ–ˆ์„ ๊ฒฝ์šฐ 0์œผ๋กœ ํ‘œ์‹œํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด๋ฏธ ๋“ค๋ฆฐ ๊ฒฝ์šฐ ์—ฐ์‚ฐ์ž‘์—…์„ ๊ฑด๋„ˆ๋œ๋‹ˆ๋‹ค. 2๊ฐœ์˜ ๋ฐฐ์—ด์„ ํƒ์‚ญํ•˜์—ฌ 2*N^2์ด์ง€๋งŒ ์ƒ์ˆ˜๋Š” ์ƒ๋žต๋ฉ๋‹ˆ๋‹ค.

 

 

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

 

๋Œ“๊ธ€