๋ชฉ๋ก๐Ÿ‘Š PS (125)

hades

[Baekjoon] 14500๋ฒˆ: ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ

๐Ÿฅ… ๋ฌธ์ œhttps://www.acmicpc.net/problem/14500 ๐Ÿ” ์„ค๊ณ„์ฒ˜์Œ์—๋Š” ์‹œ์ž‘ ์ขŒํ‘œ๋ฅผ ์žก๊ณ , ๊ทธ ์ขŒํ‘œ์—์„œ ์‹œ์ž‘ํ•˜๋Š” ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ ์ผ€์ด์Šค๋ฅผ ๋ชจ๋‘ ๋งŒ๋“ค์–ด์„œ ๊ฐ’์„ ๋„์ถœํ•˜๋ ค ํ–ˆ์œผ๋‚˜, ๋Œ€์นญ๊ณผ ํšŒ์ „๊นŒ์ง€ ๊ณ ๋ คํ–ˆ์„ ๋•Œ, ์ผ€์ด์Šค๊ฐ€ ๋„ˆ๋ฌด ๋งŽ์•„์ง„๋‹ค. ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ์˜ ํŠน์ง•์€ ์ธ์ ‘ํ•œ ์นธ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ๋”ฐ๋ผ์„œ, DFS๋ฅผ ์ด์šฉํ•˜์—ฌ 4๊ฐœ์˜ ์นธ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค. (poli) ํ•˜์ง€๋งŒ, ใ…— ๋ชจ์–‘์˜ ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๋Š” ์ธ์ ‘ํ•œ ์นธ์œผ๋กœ ํ™•์žฅํ•ด๋‚˜๊ฐ€๋Š” DFS๋กœ ๊ตฌํ•  ์ˆ˜ ์—†์œผ๋ฏ€๋กœ, ๋”ฐ๋กœ ๋งŒ๋“ค์–ด์•ผ ํ•œ๋‹ค. ใ…— ๋ชจ์–‘์„ ๋งŒ๋“œ๋Š” ๊ฐ€์žฅ ์‰ฌ์šด ๋ฐฉ๋ฒ•์€ ๅ ๋ชจ์–‘์˜ ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๋ฅผ ๋งŒ๋“ค๊ณ , ์ƒํ•˜์ขŒ์šฐ์—์„œ ํ•˜๋‚˜์”ฉ ๋นผ๋ฉด ๋œ๋‹ค. ๅ ๋ชจ์–‘์„ ๊ตฌ์„ฑํ•˜๋Š”๋ฐ, ์นธ์ด ์กด์žฌํ•  ์ˆ˜ ์žˆ๋Š” ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜๋Š” ๊ฒฝ์šฐ์—๋Š” ์ œ์™ธ๋˜์—ˆ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋ฉด ๋˜๊ณ , ์ œ์™ธ๋œ..

๐Ÿ‘Š PS/Algorithm 2024. 7. 26. 12:39
[Baekjoon] 10026๋ฒˆ: ์ ๋ก์ƒ‰์•ฝ

๐Ÿฅ… ๋ฌธ์ œhttps://www.acmicpc.net/problem/10026 ๐Ÿ” ์„ค๊ณ„์ƒํ•˜์ขŒ์šฐ๋กœ ์ธ์ ‘ํ•œ ์˜์—ญ ์ค‘ ๊ฐ™์€ ์ƒ‰์„ ๊ฐ€์ง„๋‹ค๋ฉด ํ•œ ๊ตฌ์—ญ์œผ๋กœ ์ธ์‹ํ•œ๋‹ค๋Š” ๊ฒƒ์—์„œ BFS์ž„์„ ์•Œ์•„์ฐจ๋ฆด ์ˆ˜ ์žˆ๋‹ค. ์ ๋ก์ƒ‰์•ฝ์ธ ์‚ฌ๋žŒ๊ณผ ์ ๋ก์ƒ‰์•ฝ์ด ์•„๋‹Œ ์‚ฌ๋žŒ์˜ ๊ฒฝ์šฐ๋ฅผ ๋‚˜๋ˆ„์–ด์„œ BFS๋ฅผ ์ˆ˜ํ–‰ํ•œ๋‹ค. ์ ๋ก์ƒ‰์•ฝ์ด ์•„๋‹ˆ๋ผ๋ฉด, BFS๊ฐ€ ์‹œ์ž‘๋˜๋Š” ์ง€์ ์˜ ์ƒ‰๊น”๊ณผ ๊ฐ™์•„์•ผ ํ•œ ๊ตฌ์—ญ์— ํฌํ•จ๋˜๊ณ , ์ ๋ก์ƒ‰์•ฝ์ด๋ผ๋ฉด ์‹œ์ž‘๋˜๋Š” ์ง€์ ์˜ ์ƒ‰๊น”์ด ๋นจ๊ฐ„์ƒ‰ ๋˜๋Š” ์ดˆ๋ก์ƒ‰์ด๋ฉด, ์ด์›ƒํ•œ ์ง€์ ์˜ ์ƒ‰๊น”๋„ ๋นจ๊ฐ„์ƒ‰ ๋˜๋Š” ์ดˆ๋ก์ƒ‰์ด๋ฉด ํ•œ ๊ตฌ์—ญ์— ํฌํ•จ๋˜๊ณ , ํŒŒ๋ž€์ƒ‰์˜๋ฉด ์ด์›ƒํ•œ ์ง€์ ์˜ ์ƒ‰๊น”๋„ ํŒŒ๋ž€์ƒ‰์ด์–ด์•ผ ํ•œ๋‹ค. ๐Ÿ‘Š ํ’€์ด#include #include #include using namespace std;int n;vector> painting1(100, vector(100));vector..

๐Ÿ‘Š PS/Algorithm 2024. 7. 22. 21:00