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

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

2021. 4. 12. 11:50
๋ชฉ์ฐจ
  1. ์ž…๋ ฅ
  2. ์ถœ๋ ฅ
  3. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•

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 ๋ณ€์ˆ˜๋ฅผ ํ•˜๋‚˜ ์„ ์–ธํ•˜๊ณ  ๋ถ€์‹  ๊ฒฝ์šฐ ๋‹ค์Œ ์ง€์ ์ด 0์ธ ๊ฒฝ์šฐ ์•ž์œผ๋กœ ๋‚˜์•„๊ฐ€๋„๋ก ๊ตฌํ˜„ํ•˜๋ ค๊ณ  ํ–ˆ์—ˆ๋‹ค.

๊ทผ๋ฐ ๋ญ”๊ฐ€ ์ด์ƒํ•˜๊ฒŒ ํ˜๋Ÿฌ๊ฐ€๋Š” ๊ฒƒ์„ ๊นจ๋‹ซ๊ณ  ์งˆ๋ฌธ ๊ฒŒ์‹œํŒ์„ ์ฐธ๊ณ ํ•˜๋˜ ๋„์ค‘ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณ ์ˆ˜๋ถ„์˜ ์ •๋ฆฌ๊ธ€์„ ๋ณด๊ฒŒ ๋˜์—ˆ๋‹ค.

์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ˜น์€ ์ตœ๋‹จ ๊ฒฝ๋กœ ๋ฌธ์ œ์—์„œ ๋˜๊ฒŒ ์ž์ฃผ ๋ณด์ด๋Š” ๊ดด์ˆ˜๋ถ„์ธ๋ฐ ์•„๋ฌดํŠผ...

 

์ฒซ ๋ฒˆ์งธ ๋ฌธ์žฅ์„ ์ฝ๊ณ  ์ƒ๊ฐ์ด ์งง์•˜์Œ์„ ๋ฐ”๋กœ ์ธ์ง€ํ–ˆ๋‹ค... ์ดํ›„ DFS์—์„œ BFS๋กœ ๋ณ€๊ฒฝํ–ˆ๊ณ  ๋‹ค์‹œ ์ƒ๊ฐํ•ด๋ณด์•˜๋‹ค.

 

ํ•ต์‹ฌ์€ ํ•ด๋‹น ์ง€์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ €์žฅํ•˜๋˜, ๋ฒฝ์„ ๋ถ€์‹  ๊ฒฝ์šฐ ์ด๋™ํ•˜๋ ค๋Š” ์ง€์ ์ด 0์ธ ๊ฒฝ์šฐ์—๋งŒ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.

 

์กฐ๊ฑด์„ ์ •๋ฆฌํ•ด๋ณด๋ฉด

1. ๋‹ค์Œ ์ด๋™ํ•  ๊ณณ์ด ๋ฒฝ์ด๊ณ , ๋ฒฝ์„ ๋ถ€์ˆ  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ

-> ๋ฒฝ์„ ๋ถ€์ˆ˜๊ณ  ๋‹ค์Œ ์ง€์ ์œผ๋กœ ์ด๋™ํ•˜๊ณ  ๋ฒฝ์„ ๋ถ€์ˆ  ์ˆ˜ ์žˆ๋Š” ํšŸ์ˆ˜๋ฅผ 0์œผ๋กœ ๋งŒ๋“ค์–ด์ค€๋‹ค.

 

2. ๋‹ค์Œ ์ด๋™ํ•  ๊ณณ์ด ๊ธธ์ธ ๊ฒฝ์šฐ (= 0)

-> ๋‹ค์Œ ์ง€์ ์œผ๋กœ ์ด๋™ํ•˜๊ณ  ์ด์ „ ์ง€์ ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ + 1์„ ํ•ด์ค€๋‹ค.

 

์ด๋ ‡๊ฒŒ ์ฝ”๋“œ๋ฅผ ๊ตฌํ˜„ํ•ด์„œ ์ œ์ถœ์„ ํ–ˆ๋Š”๋ฐ

์—ฅ ์‹œ๊ฐ„์ดˆ๊ณผ...?

 

์ดํ›„ ์ฝ”๋“œ๋ฅผ ๋‹ค์‹œ ๋ดค๋Š”๋ฐ ์กฐ๊ฑด์„ ์ž˜๋ชป ์„ค์ •ํ•ด์คฌ์—ˆ๋‹ค.

 

๋ฌธ์ œ๋Š” 2๋ฒˆ ์กฐ๊ฑด์ด์˜€๋‹ค. ๋‚˜๋Š” ๋‹จ์ˆœํžˆ ๋‹ค์Œ ์ด๋™ํ•  ๊ณณ์ด ๊ธธ์ธ ๊ฒฝ์šฐ๋งŒ ์กฐ๊ฑด์— ๋„ฃ์–ด์คฌ๋Š”๋ฐ ์ด ๊ฒฝ์šฐ์— ์ด์ „ ์ง€์ ์„ ๋‹ค์‹œ ๋ฐฉ๋ฌธํ•˜๊ฒŒ ๋˜๋Š” ์˜ค๋ฅ˜๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. for๋ฌธ์„ ํ†ตํ•ด ์ƒ, ํ•˜, ์ขŒ, ์šฐ 4๊ฐœ์˜ ๋ฐฉํ–ฅ์œผ๋กœ ํ•œ์นธ์”ฉ ๋‚˜์•„๊ฐ€๊ณ  ์žˆ๋Š”๋ฐ ๋งŒ์•ฝ ํ˜„์žฌ ์ง€์ ๋„ 0, ๋‹ค์Œ ์ง€์ ๋„ 0์ธ ๊ฒฝ์šฐ ๋ฌดํ•œ ๋ฃจํ”„์— ๋น ์ ธ๋ฒ„๋ฆด ์ˆ˜๊ฐ€ ์žˆ๋‹ค. (์•„๋ž˜๋กœ ๋‚ด๋ ค๊ฐ”๋‹ค๊ฐ€ ๋‹ค์‹œ ์œ„๋กœ ๋˜ ๋‹ค์‹œ ์•„๋ž˜๋กœ... ๋ฌดํ•œ ๋ฐ˜๋ณต) ๋‹ค์Œ ์ด๋™ํ•  ๊ณณ์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๊ฐ€ 0์ธ ๊ฒฝ์šฐ, ์ฆ‰ ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๊ฒฝ์šฐ ๋‹ค์Œ ์ง€์ ์œผ๋กœ ๋„˜์–ด๊ฐ€๋„๋ก ์กฐ๊ฑด์„ ์ถ”๊ฐ€ํ•ด์คฌ๊ณ  ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

 

 

์กฐ๊ฑด์„ ๋‹ค์‹œ ์ •๋ฆฌํ•ด๋ณด๋ฉด

1. ๋‹ค์Œ ์ด๋™ํ•  ๊ณณ์ด ๋ฒฝ์ด๊ณ , ๋ฒฝ์„ ๋ถ€์ˆ  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ

-> ๋ฒฝ์„ ๋ถ€์ˆ˜๊ณ  ๋‹ค์Œ ์ง€์ ์œผ๋กœ ์ด๋™ํ•˜๊ณ  ๋ฒฝ์„ ๋ถ€์ˆ  ์ˆ˜ ์žˆ๋Š” ํšŸ์ˆ˜๋ฅผ 0์œผ๋กœ ๋งŒ๋“ค์–ด์ค€๋‹ค.

 

2. ๋‹ค์Œ ์ด๋™ํ•  ๊ณณ์ด ๊ธธ์ด๊ณ  (= 0), ๋‹ค์Œ ์ง€์ ์ด ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ง€์ ์ธ ๊ฒฝ์šฐ

-> ๋‹ค์Œ ์ง€์ ์œผ๋กœ ์ด๋™ํ•˜๊ณ  ์ด์ „ ์ง€์ ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ + 1์„ ํ•ด์ค€๋‹ค.

 

์œ„ ์กฐ๊ฑด์— ๋”ฐ๋ผ ๊ณ„์† ๋ฐ˜๋ณตํ•˜๋‹ค๊ฐ€ dst์— ๋„์ฐฉํ•˜๋ฉด ์ €์žฅ๋œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ, ๋„์ฐฉํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” -1์„  ๋ฆฌํ„ดํ•˜๊ฒŒ ๊ตฌํ˜„ํ•ด์ฃผ์—ˆ๋‹ค.

 

์šฐ์„  ์œ„์˜ ๊ฐœ๋…์„ ํŒŒ์ด์ฌ์œผ๋กœ ๊ตฌํ˜„ํ•ด๋ดค๋‹ค.

 

 

C++๋กœ๋„ ๊ตฌํ˜„ํ•ด๋ดค๋‹ค. ์š”์ฆ˜์— ํŒŒ์ด์ฌ๋งŒ ์“ฐ๋‹ค๋ณด๋‹ˆ๊นŒ ๋จธ๋ฆฌ๊ฐ€ ํŒŒ์ด์ฌํ™” ๋๋‚˜๋ณด๋‹ค...

C++ ๋„ˆ๋ฌด ์–ด๋ ค์šด๋“ฏ... ์ง€์—ญ๋ณ€์ˆ˜๋กœ ์„ ์–ธํ•˜๋‹ˆ๊นŒ Segment Fault๋„ ๋œจ๊ณ ... ์•„๋ฌดํŠผ ์• ๋จน์—ˆ์Œ ใ…Žใ…Ž;;

ํ™•์‹คํžˆ ํผํฌ๋จผ์Šค๋Š” ๋”ฐ๋ผ์˜ฌ ์ˆ˜ ์—†๋Š”๋“ฏ? 50๋ฐฐ๋‚˜ ๋น ๋ฅด๋‹ค...ใ„ทใ„ทใ„ท

 

 

ใ…‹ใ…‹ใ…‹ใ…‹ cin์—์„œ ๋ถ€ํ„ฐ ์˜ค๋ฅ˜๋–ด์Œ...

 

 

์—ญ์‹œ ๊ณจ๋“œ๋ฌธ์ œ์ธ๊ฐ€... ์ข€ ๋” ์ƒ๊ฐํ•˜๊ฒŒ ๋งŒ๋“œ๋Š” ๋ฌธ์ œ๋‹ค.

์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ > DFS, BFS' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[BFS][Kotlin] 2021 ์นด์นด์˜ค ์ฑ„์šฉ์—ฐ๊ณ„ํ˜• ์ธํ„ด์‹ญ - ๊ฑฐ๋ฆฌ๋‘๊ธฐ ํ™•์ธํ•˜๊ธฐ  (0) 2022.03.20
[DFS์™€ BFS] [Python / C++] 1260. DFS์™€ BFS  (0) 2021.04.18
[DFS์™€ BFS] [Python / C++] 1707. ์ด๋ถ„ ๊ทธ๋ž˜ํ”„  (0) 2021.04.14
[DFS์™€ BFS] [Python / C++] 7562. ๋‚˜์ดํŠธ์˜ ์ด๋™.  (0) 2021.04.13
  1. ์ž…๋ ฅ
  2. ์ถœ๋ ฅ
  3. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•
'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [BFS][Kotlin] 2021 ์นด์นด์˜ค ์ฑ„์šฉ์—ฐ๊ณ„ํ˜• ์ธํ„ด์‹ญ - ๊ฑฐ๋ฆฌ๋‘๊ธฐ ํ™•์ธํ•˜๊ธฐ
  • [DFS์™€ BFS] [Python / C++] 1260. DFS์™€ BFS
  • [DFS์™€ BFS] [Python / C++] 1707. ์ด๋ถ„ ๊ทธ๋ž˜ํ”„
  • [DFS์™€ BFS] [Python / C++] 7562. ๋‚˜์ดํŠธ์˜ ์ด๋™.
kodo_o
kodo_o
iOS ๊ฟ€์žผ!
kodo_o
๐ŸŽ๐Ÿ
kodo_o
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (149)
    • ๐Ÿ”จ ํ”„๋กœ์ ํŠธ (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • ๐Ÿ’ป ๊ฐœ๋ฐœ (63)
      • iOS (30)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • ์˜ค๋Š˜์˜ ์‚ฝ์งˆ (7)
      • ์—๋Ÿฌ์™€์˜ ๋™์นจ (1)
    • โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • ๐Ÿ“š CS (6)
      • Operating System (6)
    • โ›น๏ธ ๋ผ์ดํ”„ (30)
      • 2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (12)
      • 2021 ์—ฌ๋ฆ„๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (6)
      • ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ (1)
      • ํšŒ๊ณ  (10)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ๊นƒํ—ˆ๋ธŒ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.
kodo_o
[DFS์™€ BFS] [Python / C++] 2206. ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ.
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.