๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜ ๐Ÿ’ก

[python] ์ „์—ญ๋ณ€์ˆ˜์™€ ์ง€์—ญ๋ณ€์ˆ˜ ์ •๋ฆฌ

by @ENFJ 2022. 10. 8.

์ „์—ญ๋ณ€์ˆ˜๋Š” main ์Šคํฌ๋ฆฝํŠธ์— ์„ ์–ธ๋œ๊ฒƒ์„ ๋งํ•œ๋‹ค.

15 ์ค„: cnt๋ผ๋Š” ๋ณ€์ˆ˜๋ฅผ ์ƒ์„ฑ๊ณผ ๋™์‹œ์— 5๋ผ๋Š” ๊ฐ’์„ ํ• ๋‹นํ•ด์ค€๋‹ค.

16 ์ค„: DFS1() ํ˜ธ์ถœ

17 ์ค„: DFS2() ํ˜ธ์ถœ

 

 

16๋ฒˆ์ค„ ์— DFS1() ํ˜ธ์ถœ์„ ํ•˜์—ฌ 5๋ฒˆ์ค„์— ์œ„์น˜ํ•œ DFS1()ํ•จ์ˆ˜๊ฐ€ ์‹คํ–‰๋œ๋‹ค.

print(cnt) ์ฆ‰ cnt๋ณ€์ˆ˜ ๊ฐ’์ด ์ถœ๋ ฅ๋˜๋Š”๋ฐ cnt ๋ผ๋Š” ๋ณ€์ˆ˜๊ฐ€ ์ž๊ธฐ ์ž์‹ ์˜ ์ง€์—ญ๋ณ€์ˆ˜์ธ์ง€ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.

์ž๊ธฐ์˜ ์ง€์—ญ๋ณ€์ˆ˜๊ฐ€ ์•„๋‹ˆ๋ผ๋ฉด ์ „์—ญ๋ณ€์ˆ˜์ธ์ง€ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.

๋‘˜๋‹ค ์•„๋‹ˆ๋ผ๋ฉด ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค.

์—ฌ๊ธฐ์„œ๋Š” 6๋ฒˆ์ค„์˜ cnt๋Š” ์ž๊ธฐ ์ž์‹ ์˜ ์ง€์—ญ๋ณ€์ˆ˜๊ฐ€ ์•„๋‹ˆ๋‹ค. ๊ทธ๋ ‡๊ธฐ ๋•Œ๋ฌธ์— ์ „์—ญ๋ณ€์ˆ˜๋กœ ์ž‘๋™ํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

๊ทธ๋ž˜์„œ 5๊ณผ ์ถœ๋ ฅ๋œ๋‹ค.

 

17๋ฒˆ์ค„์— DFS2() ํ˜ธ์ถœ ํ•˜์—ฌ 8๋ฒˆ์ค„์— ์œ„์น˜ํ•œ DFS2()ํ•จ์ˆ˜๊ฐ€ ์‹คํ–‰ ๋œ๋‹ค.

๋งŒ์•ฝ ๋ณ€์ˆ˜cnt ๊ฐ€ 5๊ฐ€ ๋งž๋‹ค๋ฉด cnt ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋Š” ์ฝ”๋“œ์ด๋‹ค.

๊ทธ๋Ÿฐ๋ฐ ์—ฌ๊ธฐ์„œ๋„ cnt๋Š” ์ง€์—ญ๋ณ€์ˆ˜์ธ์ง€ ๋จผ์ € ํ™•์ธํ•ด๋ณด๋‹ˆ ์•„๋‹ˆ๋‹ค. ์ „์—ญ๋ณ€์ˆ˜๋กœ ์ž‘๋™ํ•˜๊ฒŒ ๋œ๋‹ค.

๊ทธ๋ ‡๊ธฐ ๋•Œ๋ฌธ์— 5๊ฐ€ ์ถœ๋ ฅ๋œ๋‹ค.

 

๋งˆ์ง€๋ง‰ 18๋ฒˆ ์ค„ cnt ์ถœ๋ ฅ ๊ฐ’ ์€ 5

 

๊ฒฐ๊ณผ :

 

๊ฐ€ ์ถœ๋ ฅ๋œ๋‹ค.

 


์ด๋ฒˆ์—๋Š” 5๋ฒˆ์ค„์— cnt=3 ๋งŒ ์ถ”๊ฐ€ํ–ˆ๋‹ค.

 

๊ทธ๋Ÿฌ๋ฉด 6๋ฒˆ์ค„ ๋ณ€์ˆ˜ cnt๋Š” ์ถœ๋ ฅํ• ๋•Œ 15๋ฒˆ์ค„์˜ cnt=5 ๋ฅผ ์ถœ๋ ฅํ•˜์ง€ ์•Š๊ณ  ์ง€์—ญ๋ณ€์ˆ˜ 5๋ฒˆ์ค„ cnt=3 ์„ ๋ถˆ๋Ÿฌ์™€์„œ

3์„ ์ถœ๋ ฅํ•œ๋‹ค. 


10๋ฒˆ์ค„์— cnt=cnt+1 ์„ ์ถ”๊ฐ€ํ•ด๋ณด์•˜๋‹ค.  ์ด๋ ‡๊ฒŒ ๋˜๋ฉด ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•˜๋Š”๋ฐ. ๊ทธ์ด์œ ๊ฐ€ 

cnt = cnt +1 ์—์„œ cnt๋Š” ์ง€์—ญ๋ณ€์ˆ˜ ์„ ์–ธ์œผ๋กœ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ์ง€์—ญ๋ณ€์ˆ˜ ์ธ cnt์˜ ๊ฐ’์ด ์–ด๋””์—๋„ ์„ ์–ธ๋˜์–ด ์žˆ์ง€ ์•Š๋‹ค.

์ง€์—ญ๋ณ€์ˆ˜๋กœ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” 8๋ฒˆ 9๋ฒˆ ์‚ฌ์ด์— cnt = 1 ์ด๋ผ๋˜์ง€ cnt์— ๊ฐ’์„ ํ• ๋‹นํ•ด์ฃผ๋ฉด ํ•ด๊ฒฐ๋œ๋‹ค.

 

์•„๋‹ˆ๋ฉด ์ „์—ญ๋ณ€์ˆ˜๋กœ ์‚ฌ์šฉํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด 

 9๋ฒˆ์ค„ ์ฒ˜๋Ÿผ global cnt ๋ฅผ ์ฝ”๋“œ์— ๋„ฃ์–ด์ฃผ๋ฉด ์ „์—ญ๋ณ€์ˆ˜๋กœ cnt๋ฅผ ์‚ฌ์šฉํ•˜๊ฒŒ ๋œ๋‹ค.