dfs์™€ bfs

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 1260. DFS์™€ BFS

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. www.acmicpc.net/problem/1260 1260๋ฒˆ: DFS์™€ BFS ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ‰ค 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ‰ค 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ์ด์— ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ฐ„์„ ์ด ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ๊ฐ„์„ ์€ ์–‘๋ฐฉํ–ฅ์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— DFS๋ฅผ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 1707. ์ด๋ถ„ ๊ทธ๋ž˜ํ”„

www.acmicpc.net/problem/1707 1707๋ฒˆ: ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ K(2โ‰คKโ‰ค5)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ๊ฐœ์ˆ˜ V(1โ‰คVโ‰ค20,000)์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ K(2โ‰คKโ‰ค5)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ๊ฐœ์ˆ˜ V(1โ‰คVโ‰ค20,000)์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ E(1โ‰คEโ‰ค200,000)๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์ •์ ์—๋Š” 1๋ถ€ํ„ฐ V๊นŒ์ง€ ์ฐจ๋ก€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์–ด ์žˆ๋‹ค. ์ด์–ด์„œ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ E๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 7562. ๋‚˜์ดํŠธ์˜ ์ด๋™.

www.acmicpc.net/problem/7562 7562๋ฒˆ: ๋‚˜์ดํŠธ์˜ ์ด๋™ ์ฒด์ŠคํŒ ์œ„์— ํ•œ ๋‚˜์ดํŠธ๊ฐ€ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ํ•œ ๋ฒˆ์— ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์€ ์•„๋ž˜ ๊ทธ๋ฆผ์— ๋‚˜์™€์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค. ๋‚˜์ดํŠธ๋Š” ๋ช‡ ๋ฒˆ ์›€์ง์ด๋ฉด ์ด ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ์„ธ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ฒซ์งธ ์ค„์—๋Š” ์ฒด์ŠคํŒ์˜ ํ•œ ๋ณ€์˜ ๊ธธ์ด l(4 โ‰ค l โ‰ค 300)์ด ์ฃผ์–ด์ง„๋‹ค. ์ฒด์ŠคํŒ์˜ ํฌ๊ธฐ๋Š” l ร— l์ด๋‹ค. ์ฒด์ŠคํŒ์˜ ๊ฐ ์นธ์€ ๋‘ ์ˆ˜์˜ ์Œ {0, ..., l-1} ร— {0, ..., l-1}๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๋‘˜์งธ ์ค„๊ณผ ์…‹์งธ ์ค„์—๋Š” ๋‚˜์ดํŠธ๊ฐ€ ํ˜„์žฌ ์žˆ๋Š” ์นธ, ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ๊ฐ ํ…Œ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 2206. ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ.

www.acmicpc.net/problem/2206 2206๋ฒˆ: ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ Nร—M์˜ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„๋˜๋Š” ๋งต์ด ์žˆ๋‹ค. ๋งต์—์„œ 0์€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ด๊ณ , 1์€ ์ด๋™ํ•  ์ˆ˜ ์—†๋Š” ๋ฒฝ์ด ์žˆ๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹น์‹ ์€ (1, 1)์—์„œ (N, M)์˜ ์œ„์น˜๊นŒ์ง€ ์ด๋™ํ•˜๋ ค ํ•˜๋Š”๋ฐ, ์ด๋•Œ ์ตœ๋‹จ ๊ฒฝ๋กœ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1 โ‰ค N โ‰ค 1,000), M(1 โ‰ค M โ‰ค 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์— M๊ฐœ์˜ ์ˆซ์ž๋กœ ๋งต์ด ์ฃผ์–ด์ง„๋‹ค. (1, 1)๊ณผ (N, M)์€ ํ•ญ์ƒ 0์ด๋ผ๊ณ  ๊ฐ€์ •ํ•˜์ž. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋ถˆ๊ฐ€๋Šฅํ•  ๋•Œ๋Š” -1์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์ตœ๋‹จ ๊ฒฝ๋กœ ๋ฌธ์ œ์ด๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ์ฒ˜์Œ ์ ‘ํ–ˆ์„ ๋•Œ๋Š” DFS๋กœ ํ’€์–ด์•ผํ•˜๋Š” ์ค„ ์•Œ์•˜๋‹ค. ๋ฒฝ์„ ๋ถ€์…จ๋Š”์ง€ ํ™•์ธํ•˜๋Š” bool..

kodo_o
'dfs์™€ bfs' ํƒœ๊ทธ์˜ ๊ธ€ ๋ชฉ๋ก