BFS

    [PGM_1844] ๊ฒŒ์ž„ ๋งต ์ตœ๋‹จ๊ฑฐ๋ฆฌ (java)

    [PGM_1844] ๊ฒŒ์ž„ ๋งต ์ตœ๋‹จ๊ฑฐ๋ฆฌ (java)

    ๋ฌธ์ œ๋งํฌ https://programmers.co.kr/learn/courses/30/lessons/1844 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๊ฒŒ์ž„ ๋งต ์ตœ๋‹จ๊ฑฐ๋ฆฌ [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr ๋ฌธ์ œํ’€์ด ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ํ•ต์‹ฌ ์Šคํ‚ฌ ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป BFS 1. ๋ฌธ์ œ ์ดํ•ด (0,0)์„ ์‹œ์ž‘์ ์œผ๋กœ ํ•˜์—ฌ ์ • ๋ฐ˜๋Œ€ํŽธ์— ์œ„์น˜ํ•œ (n,m)์œผ๋กœ ์ด๋™ํ•˜๋Š” ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์—†๋Š”์ง€์˜ ์—ฌ๋ถ€์˜ map์ด ์ฃผ์–ด์ง„๋‹ค. ๋งŒ์•ฝ (n,m)์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” -1์„ returnํ•˜์—ฌ์ฃผ๋ฉด ๋œ๋‹ค...

    [BOJ_1261] ์•Œ๊ณ ์ŠคํŒŸ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/1261 1261๋ฒˆ: ์•Œ๊ณ ์ŠคํŒŸ ์ฒซ์งธ ์ค„์— ๋ฏธ๋กœ์˜ ํฌ๊ธฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๊ฐ€๋กœ ํฌ๊ธฐ M, ์„ธ๋กœ ํฌ๊ธฐ N (1 ≤ N, M ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” ๋ฏธ๋กœ์˜ ์ƒํƒœ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ˆซ์ž 0๊ณผ 1์ด ์ฃผ์–ด์ง„๋‹ค. 0์€ ๋นˆ ๋ฐฉ์„ ์˜๋ฏธํ•˜๊ณ , 1์€ ๋ฒฝ์„ ์˜๋ฏธ www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์•Œ๊ณ ์ŠคํŒŸ ์šด์˜์ง„์ด ๋ชจ๋‘ ๋ฏธ๋กœ์— ๊ฐ‡ํ˜”๋‹ค. ๋ฏธ๋กœ๋Š” N*M ํฌ๊ธฐ์ด๋ฉฐ, ์ด 1*1ํฌ๊ธฐ์˜ ๋ฐฉ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๋ฏธ๋กœ๋Š” ๋นˆ ๋ฐฉ ๋˜๋Š” ๋ฒฝ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , ๋นˆ ๋ฐฉ์€ ์ž์œ ๋กญ๊ฒŒ ๋‹ค๋‹ ์ˆ˜ ์žˆ์ง€๋งŒ, ๋ฒฝ์€ ๋ถ€์ˆ˜์ง€ ์•Š์œผ๋ฉด ์ด๋™ํ•  ์ˆ˜ ์—†๋‹ค. ์•Œ๊ณ ์ŠคํŒŸ ์šด์˜์ง„์€ ์—ฌ๋Ÿฌ๋ช…์ด์ง€๋งŒ, ํ•ญ์ƒ ๋ชจ๋‘ ๊ฐ™์€ ๋ฐฉ์— ์žˆ์–ด์•ผ ํ•œ๋‹ค. ์ฆ‰, ์—ฌ๋Ÿฌ ๋ช…์ด ๋‹ค๋ฅธ ๋ฐฉ์— ์žˆ์„ ์ˆ˜๋Š” ์—†๋‹ค. ์–ด๋–ค ๋ฐฉ์—์„œ ์ด..

    [BOJ_14226] ์ด๋ชจํ‹ฐ์ฝ˜ (java)

    [BOJ_14226] ์ด๋ชจํ‹ฐ์ฝ˜ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/14226 14226๋ฒˆ: ์ด๋ชจํ‹ฐ์ฝ˜ ์˜์„ ์ด๋Š” ๋งค์šฐ ๊ธฐ์˜๊ธฐ ๋•Œ๋ฌธ์—, ํšจ๋นˆ์ด์—๊ฒŒ ์Šค๋งˆ์ผ ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋ณด๋‚ด๋ ค๊ณ  ํ•œ๋‹ค. ์˜์„ ์ด๋Š” ์ด๋ฏธ ํ™”๋ฉด์— ์ด๋ชจํ‹ฐ์ฝ˜ 1๊ฐœ๋ฅผ ์ž…๋ ฅํ–ˆ๋‹ค. ์ด์ œ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ 3๊ฐ€์ง€ ์—ฐ์‚ฐ๋งŒ ์‚ฌ์šฉํ•ด์„œ ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋งŒ www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์˜์„ ์ด๋Š” ๋งค์šฐ ๊ธฐ์˜๊ธฐ ๋•Œ๋ฌธ์—, ํšจ๋นˆ์ด์—๊ฒŒ ์Šค๋งˆ์ผ ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋ณด๋‚ด๋ ค๊ณ  ํ•œ๋‹ค. ์˜์„ ์ด๋Š” ์ด๋ฏธ ํ™”๋ฉด์— ์ด๋ชจํ‹ฐ์ฝ˜ 1๊ฐœ๋ฅผ ์ž…๋ ฅํ–ˆ๋‹ค. ์ด์ œ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ 3๊ฐ€์ง€ ์—ฐ์‚ฐ๋งŒ ์‚ฌ์šฉํ•ด์„œ ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋งŒ๋“ค์–ด ๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜์„ ๋ชจ๋‘ ๋ณต์‚ฌํ•ด์„œ ํด๋ฆฝ๋ณด๋“œ์— ์ €์žฅํ•œ๋‹ค. ํด๋ฆฝ๋ณด๋“œ์— ์žˆ๋Š” ๋ชจ๋“  ์ด๋ชจํ‹ฐ์ฝ˜์„ ํ™”๋ฉด์— ๋ถ™์—ฌ๋„ฃ๊ธฐ ํ•œ๋‹ค. ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ์ค‘ ํ•˜๋‚˜๋ฅผ ์‚ญ์ œํ•œ๋‹ค..

    [BOJ_14226] ์ด๋ชจํ‹ฐ์ฝ˜ (java)

    [BOJ_14226] ์ด๋ชจํ‹ฐ์ฝ˜ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/14226 14226๋ฒˆ: ์ด๋ชจํ‹ฐ์ฝ˜ ์˜์„ ์ด๋Š” ๋งค์šฐ ๊ธฐ์˜๊ธฐ ๋•Œ๋ฌธ์—, ํšจ๋นˆ์ด์—๊ฒŒ ์Šค๋งˆ์ผ ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋ณด๋‚ด๋ ค๊ณ  ํ•œ๋‹ค. ์˜์„ ์ด๋Š” ์ด๋ฏธ ํ™”๋ฉด์— ์ด๋ชจํ‹ฐ์ฝ˜ 1๊ฐœ๋ฅผ ์ž…๋ ฅํ–ˆ๋‹ค. ์ด์ œ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ 3๊ฐ€์ง€ ์—ฐ์‚ฐ๋งŒ ์‚ฌ์šฉํ•ด์„œ ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋งŒ www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์˜์„ ์ด๋Š” ๋งค์šฐ ๊ธฐ์˜๊ธฐ ๋•Œ๋ฌธ์—, ํšจ๋นˆ์ด์—๊ฒŒ ์Šค๋งˆ์ผ ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋ณด๋‚ด๋ ค๊ณ  ํ•œ๋‹ค. ์˜์„ ์ด๋Š” ์ด๋ฏธ ํ™”๋ฉด์— ์ด๋ชจํ‹ฐ์ฝ˜ 1๊ฐœ๋ฅผ ์ž…๋ ฅํ–ˆ๋‹ค. ์ด์ œ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ 3๊ฐ€์ง€ ์—ฐ์‚ฐ๋งŒ ์‚ฌ์šฉํ•ด์„œ ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋งŒ๋“ค์–ด ๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜์„ ๋ชจ๋‘ ๋ณต์‚ฌํ•ด์„œ ํด๋ฆฝ๋ณด๋“œ์— ์ €์žฅํ•œ๋‹ค. ํด๋ฆฝ๋ณด๋“œ์— ์žˆ๋Š” ๋ชจ๋“  ์ด๋ชจํ‹ฐ์ฝ˜์„ ํ™”๋ฉด์— ๋ถ™์—ฌ๋„ฃ๊ธฐ ํ•œ๋‹ค. ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ์ค‘ ํ•˜๋‚˜๋ฅผ ์‚ญ์ œํ•œ๋‹ค..

    BFS๋กœ ์ตœ์†Œ๋น„์šฉ ๋ฌธ์ œ ํ•ด๊ฒฐํ•˜๊ธฐ

    BFS๋กœ ์ตœ์†Œ๋น„์šฉ ๋ฌธ์ œ ํ•ด๊ฒฐํ•˜๊ธฐ

    ๋„์ž… BFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋ชฉ์ ์€ ๊ทธ๋ž˜ํ”„์—์„œ ๋ชจ๋“  ์ •์ ์„ ํ•œ๋ฒˆ์”ฉ๋งŒ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•œ ๊ฒƒ์ž…๋‹ˆ๋‹ค. BFS๊ฐ€ ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰์กฐ๊ฑด์ด๋ผ๋Š” ์„ฑ์งˆ ๋•Œ๋ฌธ์— ๋ช‡๊ฐ€์ง€ ์กฐ๊ฑด๋งŒ ์„ฑ๋ฆฝํ•˜๋ฉด ์ตœ์†Œ๋น„์šฉ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. BFS๋ž€? BFS ๊ทธ๋ž˜ํ”„ ์„ค๋ช… ์ฐธ๊ณ ํ•˜๊ธฐ [Algorithm] ๊ทธ๋ž˜ํ”„๋ž€? ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰์•Œ๊ณ ๋ฆฌ์ฆ˜(DFS,BFS) ๋„์ž… ๊ทธ๋ž˜ํ”„๋Š” ์ •์ ๊ณผ ๊ฐ„์„ ์œผ๋กœ ๊ตฌ์„ฑ๋˜๋Š” ์ค‘์š”ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์ด๋ฒˆ ์‹œ๊ฐ„์—๋Š” ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•œ ์šฉ์–ด์™€ ๊ทธ๋ž˜ํ”„๋ฅผ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ• ๊ทธ๋ฆฌ๊ณ  ๊ทธ๋ž˜ํ”„๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜ํ”„ cnu-jinseop.tistory.com BFS๋Š” ๊ทธ๋ž˜ํ”„์˜ ํƒ์ƒ‰์—์„œ ์‚ฌ์šฉ๋˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. DFS์™€ ๋™์ผํ•˜๊ฒŒ ๋ชจ๋“  ์ •์ ์„ ํ•œ๋ฒˆ์”ฉ๋งŒ ํ™•์ธํ•  ๋•Œ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. BFS๋Š” ๋„ˆ๋น„๋ฅผ ์šฐ์„ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ๊ธฐ๋Šฅ์„ ์ˆ˜ํ–‰ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ตœ์†Œ๋น„์šฉ ๋ฌธ์ œ๋ฅผ ํ•ด..

    [BOJ_7576] ํ† ๋งˆํ†  (java)

    [BOJ_7576] ํ† ๋งˆํ†  (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/7576 7576๋ฒˆ: ํ† ๋งˆํ†  ์ฒซ ์ค„์—๋Š” ์ƒ์ž์˜ ํฌ๊ธฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋‘ ์ •์ˆ˜ M,N์ด ์ฃผ์–ด์ง„๋‹ค. M์€ ์ƒ์ž์˜ ๊ฐ€๋กœ ์นธ์˜ ์ˆ˜, N์€ ์ƒ์ž์˜ ์„ธ๋กœ ์นธ์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹จ, 2 ≤ M,N ≤ 1,000 ์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ๋Š” ํ•˜๋‚˜์˜ ์ƒ์ž์— ์ €์žฅ๋œ ํ† ๋งˆํ†  www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์ฒ ์ˆ˜์˜ ํ† ๋งˆํ†  ๋†์žฅ์—์„œ๋Š” ํ† ๋งˆํ† ๋ฅผ ๋ณด๊ด€ํ•˜๋Š” ํฐ ์ฐฝ๊ณ ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ํ† ๋งˆํ† ๋Š” ์•„๋ž˜์˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ๊ฒฉ์ž ๋ชจ์–‘ ์ƒ์ž์˜ ์นธ์— ํ•˜๋‚˜์”ฉ ๋„ฃ์–ด์„œ ์ฐฝ๊ณ ์— ๋ณด๊ด€ํ•œ๋‹ค. ์ฐฝ๊ณ ์— ๋ณด๊ด€๋˜๋Š” ํ† ๋งˆํ† ๋“ค ์ค‘์—๋Š” ์ž˜ ์ต์€ ๊ฒƒ๋„ ์žˆ์ง€๋งŒ, ์•„์ง ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† ๋“ค๋„ ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ๋ณด๊ด€ ํ›„ ํ•˜๋ฃจ๊ฐ€ ์ง€๋‚˜๋ฉด, ์ต์€ ํ† ๋งˆํ† ๋“ค์˜ ์ธ์ ‘ํ•œ ๊ณณ์— ์žˆ๋Š” ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† ๋“ค์€ ์ต์€ ํ† ..

    [BOJ_11724] ์—ฐ๊ฒฐ์š”์†Œ (java)

    [BOJ_11724] ์—ฐ๊ฒฐ์š”์†Œ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/11724 11724๋ฒˆ: ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ๊ฐ„์„ ์˜ ์–‘ ๋์  u์™€ v๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ u, v ≤ N, u ≠ v) ๊ฐ™์€ ๊ฐ„์„ ์€ ํ•œ ๋ฒˆ๋งŒ ์ฃผ www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ๋ฐฉํ–ฅ ์—†๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์—ฐ๊ฒฐ ์š”์†Œ (Connected Component)์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ๊ฐ„์„ ์˜ ์–‘ ๋์  u์™€ v๊ฐ€..