๋์ด๋ : ๊ณจ๋ 4 ๊ฑธ๋ฆฐ ์๊ฐ : ์ค๋ ๊ฑธ๋ฆผ ๋ฌธ์ ์ด๋ถ ๊ทธ๋ํ ๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ ๊ทธ๋ํ์ ์ ์ ์ ์งํฉ์ ๋๋ก ๋ถํ ํ์ฌ, ๊ฐ ์งํฉ์ ์ํ ์ ์ ๋ผ๋ฆฌ๋ ์๋ก ์ธ์ ํ์ง ์๋๋ก ๋ถํ ํ ์ ์์ ๋, ๊ทธ๋ฌํ ๊ทธ๋ํ๋ฅผ ํน๋ณํ ์ด๋ถ ๊ทธ๋ํ (Bipartite Graph) ๋ผ ๋ถ๋ฅธ๋ค. ๊ทธ๋ํ๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ก์ ๋, ์ด ๊ทธ๋ํ๊ฐ ์ด๋ถ ๊ทธ๋ํ์ธ์ง ์๋์ง ํ๋ณํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ํ์ด bfs๋ก ์ํํ๋ฉด์ ๋ ๊ฐ์ง ์์ผ๋ก ์น ํ๊ธฐ (1, -1) ์ด๋ฏธ ์น ํด์ง ๊ณณ์ด ๋ค๋ฅธ ์์ผ๋ก ์น ํด์ ธ์ผ ํ๋ค๋ฉด ์ด๋ถ ๊ทธ๋ํ๊ฐ ์๋ ์ฝ๋ #include #include #include #include using namespace std; vector vec[20001]; bool bfs(vector& check, int start) { queue..
๋์ด๋ : ๊ณจ๋ 4 ๊ฑธ๋ฆฐ ์๊ฐ : ์ค๋ ๊ฑธ๋ฆผ ๋ฌธ์ ๋ฒฝ ๋ถ์๊ณ ์ด๋ํ๊ธฐ ๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ N×M์ ํ๋ ฌ๋ก ํํ๋๋ ๋งต์ด ์๋ค. ๋งต์์ 0์ ์ด๋ํ ์ ์๋ ๊ณณ์ ๋ํ๋ด๊ณ , 1์ ์ด๋ํ ์ ์๋ ๋ฒฝ์ด ์๋ ๊ณณ์ ๋ํ๋ธ๋ค. ๋น์ ์ (1, 1)์์ (N, M)์ ์์น๊น์ง ์ด๋ํ๋ ค ํ๋๋ฐ, ์ด๋ ์ต๋จ ๊ฒฝ๋ก๋ก ์ด๋ํ๋ ค ํ๋ค. ์ต๋จ๊ฒฝ๋ก๋ ๋งต์์ ๊ฐ์ฅ ์ ์ ๊ฐ์์ ์นธ์ ์ง๋๋ ๊ฒฝ๋ก๋ฅผ ๋งํ๋๋ฐ, ์ด๋ ์์ํ๋ ์นธ๊ณผ ๋๋๋ ์นธ๋ ํฌํจํด์ ์ผ๋ค. ๋ง์ฝ์ ์ด๋ํ๋ ๋์ค์ ํ ๊ฐ์ ๋ฒฝ์ ๋ถ์๊ณ ์ด๋ํ๋ ๊ฒ์ด ์ข ๋ ๊ฒฝ๋ก๊ฐ ์งง์์ง๋ค๋ฉด, ๋ฒฝ์ ํ ๊ฐ ๊น์ง ๋ถ์๊ณ ์ด๋ํ์ฌ๋ ๋๋ค. ํ ์นธ์์ ์ด๋ํ ์ ์๋ ์นธ์ ์ํ์ข์ฐ๋ก ์ธ์ ํ ์นธ์ด๋ค. ๋งต์ด ์ฃผ์ด์ก์ ๋, ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํด ๋ด๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ํ์ด ๋ชจ๋ ๊ฒฝ๋ก๋ฅผ ์ดํด๋ณผ ํ์์..
๋์ด๋ : ๊ณจ๋ 4 ๊ฑธ๋ฆฐ ์๊ฐ : ใ ใ .. ์ค๋ ๊ฑธ๋ฆผ ๋ฌธ์ ์๊ธฐ ์์ด ๋ฌธ์ ๋ฐ๋ก๊ฐ๊ธฐ ํ์ด bfs๋ฅผ ์ด์ฉํ์ฌ ๋จน์ ์ ์๋ ๊ณ ๊ธฐ ์ฐพ๊ธฐ + ์์ด๋ก๋ถํฐ์ ๊ฑฐ๋ฆฌ ์ฐพ๊ธฐ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ๊ฐ๊น์ด ๋จน์ ์ ์๋ ๊ณ ๊ธฐ๋ค ์ฐพ๊ธฐ ๊ทธ ์ค ๊ฐ์ฅ ์ผ์ชฝ ์์ ์๋ ๊ณ ๊ธฐ ์ฐพ๊ธฐ ์์ด๊ฐ ํด๋น ๋ฌผ๊ณ ๊ธฐ์ ์์น๋ก ์ด๋ํด์ ๋จน๊ณ , ๋จน์ ๋ฌผ๊ณ ๊ธฐ ๊ฐ์๊ฐ size์ ๊ฐ์์ง๋ฉด size ํค์ฐ๊ธฐ ์์ด๋ณด๋ค ์์ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์์ ๋๊น์ง ๋ฐ๋ณต ์ฝ๋ #include #include #include using namespace std; struct shark { int r; int c; int size = 2; }; struct fish { int r; int c; int distance = 0; fish(int rp, int cp, int dist) { r = rp..
๋์ด๋ : ๊ณจ๋ 4 ๊ฑธ๋ฆฐ ์๊ฐ : 40๋ถ ๋ฌธ์ ์ํ๋ฒณ ๋ฌธ์ ๋ฐ๋ก๊ฐ๊ธฐ ์๊ฐ ์ ํ ๋ฉ๋ชจ๋ฆฌ ์ ํ ์ ์ถ ์ ๋ต ๋ง์ ์ฌ๋ ์ ๋ต ๋น์จ 2 ์ด 256 MB 49866 15734 9600 29.155% ์ธ๋ก R์นธ, ๊ฐ๋ก C์นธ์ผ๋ก ๋ ํ ๋ชจ์์ ๋ณด๋๊ฐ ์๋ค. ๋ณด๋์ ๊ฐ ์นธ์๋ ๋๋ฌธ์ ์ํ๋ฒณ์ด ํ๋์ฉ ์ ํ ์๊ณ , ์ข์ธก ์๋จ ์นธ (1ํ 1์ด) ์๋ ๋ง์ด ๋์ฌ ์๋ค. ๋ง์ ์ํ์ข์ฐ๋ก ์ธ์ ํ ๋ค ์นธ ์ค์ ํ ์นธ์ผ๋ก ์ด๋ํ ์ ์๋๋ฐ, ์๋ก ์ด๋ํ ์นธ์ ์ ํ ์๋ ์ํ๋ฒณ์ ์ง๊ธ๊น์ง ์ง๋์จ ๋ชจ๋ ์นธ์ ์ ํ ์๋ ์ํ๋ฒณ๊ณผ๋ ๋ฌ๋ผ์ผ ํ๋ค. ์ฆ, ๊ฐ์ ์ํ๋ฒณ์ด ์ ํ ์นธ์ ๋ ๋ฒ ์ง๋ ์ ์๋ค. ์ข์ธก ์๋จ์์ ์์ํด์, ๋ง์ด ์ต๋ํ ๋ช ์นธ์ ์ง๋ ์ ์๋์ง๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ง์ด ์ง๋๋ ์นธ์ ์ข์ธก ์๋จ์ ์นธ๋ ํฌํจ๋๋ค. ํ..
๋์ด๋ : ๊ณจ๋ 5 ๊ฑธ๋ฆฐ ์๊ฐ : 25๋ถ ๋ฌธ์ ์ ๋ก์์ฝ ๋ฌธ์ ๋ฐ๋ก๊ฐ๊ธฐ ๋ฌธ์ ์ ๋ก์์ฝ์ ๋นจ๊ฐ์๊ณผ ์ด๋ก์์ ์ฐจ์ด๋ฅผ ๊ฑฐ์ ๋๋ผ์ง ๋ชปํ๋ค. ๋ฐ๋ผ์, ์ ๋ก์์ฝ์ธ ์ฌ๋์ด ๋ณด๋ ๊ทธ๋ฆผ์ ์๋ ์ฌ๋์ด ๋ณด๋ ๊ทธ๋ฆผ๊ณผ๋ ์ข ๋ค๋ฅผ ์ ์๋ค. ํฌ๊ธฐ๊ฐ N×N์ธ ๊ทธ๋ฆฌ๋์ ๊ฐ ์นธ์ R(๋นจ๊ฐ), G(์ด๋ก), B(ํ๋) ์ค ํ๋๋ฅผ ์์น ํ ๊ทธ๋ฆผ์ด ์๋ค. ๊ทธ๋ฆผ์ ๋ช ๊ฐ์ ๊ตฌ์ญ์ผ๋ก ๋๋์ด์ ธ ์๋๋ฐ, ๊ตฌ์ญ์ ๊ฐ์ ์์ผ๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๋, ๊ฐ์ ์์์ด ์ํ์ข์ฐ๋ก ์ธ์ ํด ์๋ ๊ฒฝ์ฐ์ ๋ ๊ธ์๋ ๊ฐ์ ๊ตฌ์ญ์ ์ํ๋ค. (์์์ ์ฐจ์ด๋ฅผ ๊ฑฐ์ ๋๋ผ์ง ๋ชปํ๋ ๊ฒฝ์ฐ๋ ๊ฐ์ ์์์ด๋ผ ํ๋ค) ์๋ฅผ ๋ค์ด, ๊ทธ๋ฆผ์ด ์๋์ ๊ฐ์ ๊ฒฝ์ฐ์ RRRBB GGBBB BBBRR BBRRR RRRRR ์ ๋ก์์ฝ์ด ์๋ ์ฌ๋์ด ๋ดค์ ๋ ๊ตฌ์ญ์ ์๋ ์ด 4๊ฐ์ด๋ค. (๋นจ๊ฐ 2, ํ๋..
๋์ด๋ : ๊ณจ๋ 5 ๊ฑธ๋ฆฐ ์๊ฐ : 1์๊ฐ ๋ฌธ์ ์ฐ๊ตฌ์ ๋ฌธ์ ๋ฐ๋ก๊ฐ๊ธฐ ์๊ธฐ 2012๋ ! ๋๋์ด 2๋ ๊ฐ ์๋ง์ ๊ตญ๋ฏผ๋ค์ ๊ธฐ๋ค๋ฆฌ๊ฒ ํ ๊ฒ์ ACM Craft (Association of Construction Manager Craft)๊ฐ ๋ฐ๋งค๋์๋ค. ์ด ๊ฒ์์ ์ง๊ธ๊น์ง ๋์จ ๊ฒ์๋ค๊ณผ๋ ๋ค๋ฅด๊ฒ ACMํฌ๋ํํธ๋ ๋ค์ด๋๋ฏนํ ๊ฒ์ ์งํ์ ์ํด ๊ฑด๋ฌผ์ ์ง๋ ์์๊ฐ ์ ํด์ ธ ์์ง ์๋ค. ์ฆ, ์ฒซ ๋ฒ์งธ ๊ฒ์๊ณผ ๋ ๋ฒ์งธ ๊ฒ์์ด ๊ฑด๋ฌผ์ ์ง๋ ์์๊ฐ ๋ค๋ฅผ ์๋ ์๋ค. ๋งค ๊ฒ์์์ ์ ๊ฑด๋ฌผ์ ์ง๋ ์์๊ฐ ์ฃผ์ด์ง๋ค. ๋ํ ๋ชจ๋ ๊ฑด๋ฌผ์ ๊ฐ๊ฐ ๊ฑด์ค์ ์์ํ์ฌ ์์ฑ์ด ๋ ๋๊น์ง Delay๊ฐ ์กด๋ฌธ์ ์ธ์ฒด์ ์น๋ช ์ ์ธ ๋ฐ์ด๋ฌ์ค๋ฅผ ์ฐ๊ตฌํ๋ ์ฐ๊ตฌ์์์ ๋ฐ์ด๋ฌ์ค๊ฐ ์ ์ถ๋์๋ค. ๋คํํ ๋ฐ์ด๋ฌ์ค๋ ์์ง ํผ์ง์ง ์์๊ณ , ๋ฐ์ด๋ฌ์ค์ ํ์ฐ์ ๋ง๊ธฐ ์ํด์ ์ฐ..
๋์ด๋ : ๊ณจ๋ 3 ๊ฑธ๋ฆฐ ์๊ฐ : 45๋ถ ๋ฌธ์ ํํฐ ๋ฌธ์ ๋ฐ๋ก๊ฐ๊ธฐ ๋ฌธ์ N๊ฐ์ ์ซ์๋ก ๊ตฌ๋ถ๋ ๊ฐ๊ฐ์ ๋ง์์ ํ ๋ช ์ ํ์์ด ์ด๊ณ ์๋ค. ์ด๋ ๋ ์ด N๋ช ์ ํ์์ด X (1 ≤ X ≤ N)๋ฒ ๋ง์์ ๋ชจ์ฌ์ ํํฐ๋ฅผ ๋ฒ์ด๊ธฐ๋ก ํ๋ค. ์ด ๋ง์ ์ฌ์ด์๋ ์ด M๊ฐ์ ๋จ๋ฐฉํฅ ๋๋ก๋ค์ด ์๊ณ i๋ฒ์งธ ๊ธธ์ ์ง๋๋๋ฐ Ti(1 ≤ Ti ≤ 100)์ ์๊ฐ์ ์๋นํ๋ค. ๊ฐ๊ฐ์ ํ์๋ค์ ํํฐ์ ์ฐธ์ํ๊ธฐ ์ํด ๊ฑธ์ด๊ฐ์ ๋ค์ ๊ทธ๋ค์ ๋ง์๋ก ๋์์์ผ ํ๋ค. ํ์ง๋ง ์ด ํ์๋ค์ ์๋ ๊ฒ์๋ฌ์ ์ต๋จ ์๊ฐ์ ์ค๊ณ ๊ฐ๊ธฐ๋ฅผ ์ํ๋ค. ์ด ๋๋ก๋ค์ ๋จ๋ฐฉํฅ์ด๊ธฐ ๋๋ฌธ์ ์๋ง ๊ทธ๋ค์ด ์ค๊ณ ๊ฐ๋ ๊ธธ์ด ๋ค๋ฅผ์ง๋ ๋ชจ๋ฅธ๋ค. N๋ช ์ ํ์๋ค ์ค ์ค๊ณ ๊ฐ๋๋ฐ ๊ฐ์ฅ ๋ง์ ์๊ฐ์ ์๋นํ๋ ํ์์ ๋๊ตฌ์ผ์ง ๊ตฌํ์ฌ๋ผ. ํ์ด ๋ชจ๋ ์ ์์ X๊น์ง์ ์๊ฐ๊ณผ X์์ ๋ชจ๋ ์ ๊น์ง..
๋์ด๋ : ๊ณจ๋ 5 ๊ฑธ๋ฆฐ ์๊ฐ : 30๋ถ ๋ฌธ์ ์ต์๋น์ฉ ๊ตฌํ๊ธฐ ๋ฌธ์ ๋ฐ๋ก๊ฐ๊ธฐ N๊ฐ์ ๋์๊ฐ ์๋ค. ๊ทธ๋ฆฌ๊ณ ํ ๋์์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋์์ ๋์ฐฉํ๋ M๊ฐ์ ๋ฒ์ค๊ฐ ์๋ค. ์ฐ๋ฆฌ๋ A๋ฒ์งธ ๋์์์ B๋ฒ์งธ ๋์๊น์ง ๊ฐ๋๋ฐ ๋๋ ๋ฒ์ค ๋น์ฉ์ ์ต์ํ ์ํค๋ ค๊ณ ํ๋ค. A๋ฒ์งธ ๋์์์ B๋ฒ์งธ ๋์๊น์ง ๊ฐ๋๋ฐ ๋๋ ์ต์๋น์ฉ์ ์ถ๋ ฅํ์ฌ๋ผ. ๋์์ ๋ฒํธ๋ 1๋ถํฐ N๊น์ง์ด๋ค. ํ์ด ๋ค์ต์คํธ๋ผ ๊ธฐ๋ณธ ๊ตฌํ์ ์ด์ฉํด์ ํผ๋ค. ๋ค์ต์คํธ๋ผ ๊ฐ๋ ๋ฐ๋ก๊ฐ๊ธฐ ์ฝ๋ #include #include #include using namespace std; int main() { // ์ต์๋น์ฉ ๋ฌธ์ => bfs / ๊ทธ๋ํ ํ์(๋ค์ต์คํธ๋ผ) // N 10^3์ดํ M 10^6 ์ดํ // ์ถ๋ฐ, ๋์ฐฉ, ๋น์ฉ // ๋น์ฉ 10^6 ์ดํ // ๋ง์ง๋ง (์ถ๋ฐ..
Comment