λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

크루슀칼

Algorithm/Programmers 2022. 3. 16. [Programmers] μ§€ν˜• 이동 [Programmers] μ§€ν˜• 이동 JAVA 문제 : μ§€ν˜• 이동 문제 μ„€λͺ… N * N 크기의 μ§€ν˜•μ΄ 있고 μ§€ν˜•λ§ˆλ‹€ 각각의 높이가 μžˆμŠ΅λ‹ˆλ‹€. μ§€ν˜•μ˜ 높이차가 정해진 κ°’ μ΄ν•˜μ΄λ©΄ 자유둭게 이동할 수 μžˆμ§€λ§Œ, 정해진 κ°’ 보닀 차이가 λ†’μœΌλ©΄ 사닀리λ₯Ό μ„€μΉ˜ν•΄μ•Ό 이동할 수 μžˆμŠ΅λ‹ˆλ‹€. μ΄λ•Œ μ‚¬λ‹€λ¦¬μ˜ λ†’μ΄λŠ” μΈμ ‘ν•œ μ§€ν˜•μ˜ 높이 차이고, μ‚¬λ‹€λ¦¬μ˜ μˆ˜λŠ” μ œν•œμ΄ μ—†μ§€λ§Œ μ‚¬λ‹€λ¦¬λ“€μ˜ 높이합이 μ΅œμ†Œν•œμ΄ λ˜λ„λ‘ μ„€μΉ˜ν•˜μ—¬ λͺ¨λ“  μ§€ν˜•λΌλ¦¬ μ—°κ²°λ˜κ²Œ ν•΄μ•Ό ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€. Solution bfs, 크루슀칼 μ•Œκ³ λ¦¬μ¦˜ μš°μ„  bfs둜 μ„œλ‘œ 사닀리 없이 이동할 수 μžˆλŠ” μ§€ν˜•λ“€μ„ ꡬ별해 μ£Όκ³  각각 번호(사닀리 없이 이동할 수 μžˆλŠ” 지역별 번호)λ₯Ό ν• λ‹Ήν•΄ μ€λ‹ˆλ‹€. μ΄λ•Œ μΈμ ‘ν•œ μ§€ν˜•μ˜ 높이차가 주어진 κ°’ 보닀 μ»€μ„œ 이동을 λͺ»ν•˜λŠ” μ§€ν˜•μ—μ„œλŠ” 크루슀칼 ..
Algorithm/BOJ 2022. 3. 15. [BOJ] ν–‰μ„± 터널(2887) [λ°±μ€€(BOJ)] 2887_ν–‰μ„± 터널 JAVA 문제 : BOJ_2887번 ν–‰μ„± 터널 문제 μ„€λͺ… 3개의 μ’Œν‘œ (x,y,z)둜 된 N 개의 행성이 μžˆμŠ΅λ‹ˆλ‹€. 두 행성을 μ—°κ²°ν•  수 μžˆλŠ” λΉ„μš©μ€ ν–‰μ„±μ˜ 각 μ’Œν‘œμ˜ μ°¨ 쀑 μ΅œμ†Ÿκ°’μ΄λΌκ³  ν•©λ‹ˆλ‹€. μ΄λ•Œ λͺ¨λ“  행성을 ν„°λ„λ‘œ μ—°κ²°ν•  λ•Œ μ΅œμ†Œ λΉ„μš©μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€. Solution 크루슀칼 μ•Œκ³ λ¦¬μ¦˜ λͺ¨λ“  λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” μ΅œμ†Œ λΉ„μš©μ˜ 터널을 ꡬ해야 ν•˜κΈ° λ•Œλ¬Έμ— 크루슀칼 μ•Œκ³ λ¦¬μ¦˜μ„ μ‚¬μš©ν•΄μ•Ό ν•©λ‹ˆλ‹€. 주어진 터널이 μ—†κΈ° λ•Œλ¬Έμ— 터널듀을 λΉ„κ΅ν•˜λ©΄μ„œ μ΅œμ†Ÿκ°’μ˜ 터널을 μ°Ύμ•„μ•Ό ν•©λ‹ˆλ‹€. μ΄λ•Œ ν–‰μ„±μ˜ κ°œμˆ˜λŠ” μ΅œλŒ€ 100,000이 μ£Όμ–΄μ§€λ―€λ‘œ, λͺ¨λ“  행성을 μ„œλ‘œ 비ꡐ해 μ€€λ‹€λ©΄ μ‹œκ°„ μ΄ˆκ³Όκ°€ λ°œμƒν•©λ‹ˆλ‹€. 잘 생각해 보면 ν–‰μ„± κ°„μ˜ μ΅œμ†Ÿκ°’μ€ 항상 x, y, z κ°’μ˜ 차의 μ΅œμ†Ÿκ°’ 쀑 ν•˜λ‚˜μ΄κΈ° λ•Œ..

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”