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

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

2021. 4. 13. 16:07
๋ชฉ์ฐจ
  1. ์ž…๋ ฅ
  2. ์ถœ๋ ฅ
  3. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•

www.acmicpc.net/problem/7562

 

7562๋ฒˆ: ๋‚˜์ดํŠธ์˜ ์ด๋™

์ฒด์ŠคํŒ ์œ„์— ํ•œ ๋‚˜์ดํŠธ๊ฐ€ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ํ•œ ๋ฒˆ์— ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์€ ์•„๋ž˜ ๊ทธ๋ฆผ์— ๋‚˜์™€์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค. ๋‚˜์ดํŠธ๋Š” ๋ช‡ ๋ฒˆ ์›€์ง์ด๋ฉด ์ด ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜

www.acmicpc.net

 

 

์ž…๋ ฅ

์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ์„ธ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ฒซ์งธ ์ค„์—๋Š” ์ฒด์ŠคํŒ์˜ ํ•œ ๋ณ€์˜ ๊ธธ์ด l(4 โ‰ค l โ‰ค 300)์ด ์ฃผ์–ด์ง„๋‹ค. ์ฒด์ŠคํŒ์˜ ํฌ๊ธฐ๋Š” l ร— l์ด๋‹ค. ์ฒด์ŠคํŒ์˜ ๊ฐ ์นธ์€ ๋‘ ์ˆ˜์˜ ์Œ {0, ..., l-1} ร— {0, ..., l-1}๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๋‘˜์งธ ์ค„๊ณผ ์…‹์งธ ์ค„์—๋Š” ๋‚˜์ดํŠธ๊ฐ€ ํ˜„์žฌ ์žˆ๋Š” ์นธ, ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค ๋‚˜์ดํŠธ๊ฐ€ ์ตœ์†Œ ๋ช‡ ๋ฒˆ๋งŒ์— ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์ถœ๋ ฅํ•œ๋‹ค.


ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•

BFS ํ™œ์šฉ ๋ฌธ์ œ์ด๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๋ฒ”์œ„๋Š” ์ด 8๊ฐœ๋กœ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)

 

๋‹ค๋ฅธ BFS ๋ฌธ์ œ์™€ ๋™์ผํ•˜๊ฒŒ ๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•ด ๋‹ค์Œ ์ด๋™ ์ขŒํ‘œ๋ฅผ ๊ตฌํ•˜๊ณ 

๋ฒ”์œ„ ์ด๋‚ด์— ๋“ค์–ด์˜จ ๊ฒฝ์šฐ์— ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•˜๊ณ  ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ขŒํ‘œ์ธ ๊ฒฝ์šฐ ํ•ด๋‹น ์ขŒํ‘œ์— ๊ทธ ํšŸ์ˆ˜๋ฅผ ๊ธฐ๋กํ•ด์ฃผ๋ฉด ๋œ๋‹ค. 

 

๊ฐ„๋‹จํ•œ ๋ฌธ์ œ์ด๋ฏ€๋กœ ์ถ”๊ฐ€์ ์ธ ์„ค๋ช…์€ ํ•„์š” ์—†์„ ๊ฒƒ ๊ฐ™๋‹ค.

 

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

 

 

C++๋กœ๋„ ๊ตฌํ˜„ํ•ด๋ดค๋‹ค.

 

 

 

 

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

'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ > 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++] 2206. ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ.  (0) 2021.04.12
  1. ์ž…๋ ฅ
  2. ์ถœ๋ ฅ
  3. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•
'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [BFS][Kotlin] 2021 ์นด์นด์˜ค ์ฑ„์šฉ์—ฐ๊ณ„ํ˜• ์ธํ„ด์‹ญ - ๊ฑฐ๋ฆฌ๋‘๊ธฐ ํ™•์ธํ•˜๊ธฐ
  • [DFS์™€ BFS] [Python / C++] 1260. DFS์™€ BFS
  • [DFS์™€ BFS] [Python / C++] 1707. ์ด๋ถ„ ๊ทธ๋ž˜ํ”„
  • [DFS์™€ BFS] [Python / C++] 2206. ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ.
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++] 7562. ๋‚˜์ดํŠธ์˜ ์ด๋™.
์ƒ๋‹จ์œผ๋กœ

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

๋‹จ์ถ•ํ‚ค

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

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

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

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

๋ชจ๋“  ์˜์—ญ

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

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