๋‚ด ์ธ์ƒ์—์„œ ๋ฏฟ์„ ๊ฑด ์˜ค์ง ๋‚˜ ์ž์‹ ๋ฟ!

The only one you can truly trust is yourself.

๊ฒŒ์ž„ ํ”„๋กœ๊ทธ๋ž˜๋ฐ/Python ํ”„๋กœ๊ทธ๋ž˜๋ฐ

[PCCP ๋ชจ์˜๊ณ ์‚ฌ#2] ๋ณด๋ฌผ ์ง€๋„ (๊ธธ์ฐพ๊ธฐ) - ๋ฏธ์™„๋ฃŒ

๐ŸŽฎinspirer9 2023. 3. 12. 09:00
728x90
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ ์„ค๋ช…

์ง„์ˆ˜๋Š” ๋ณด๋ฌผ์ด ๋ฌปํžŒ ์žฅ์†Œ์™€ ํ•จ์ •์ด ํ‘œ์‹œ๋œ ๋ณด๋ฌผ ์ง€๋„๋ฅผ ์ด์šฉํ•ด ๋ณด๋ฌผ์„ ์ฐพ์œผ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ๋ณด๋ฌผ์ง€๋„๋Š” ๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ n, ์„ธ๋กœ ๊ธธ์ด๊ฐ€ m์ธ ์ง์‚ฌ๊ฐํ˜• ๋ชจ์–‘์ž…๋‹ˆ๋‹ค.

๋งจ ์™ผ์ชฝ ์•„๋ž˜ ์นธ์˜ ์ขŒํ‘œ๋ฅผ (1, 1)์œผ๋กœ, ๋งจ ์˜ค๋ฅธ์ชฝ ์œ„ ์นธ์˜ ์ขŒํ‘œ๋ฅผ (n, m)์œผ๋กœ ๋‚˜ํƒ€๋ƒˆ์„ ๋•Œ, ๋ณด๋ฌผ์€ (n, m) ์ขŒํ‘œ์— ๋ฌปํ˜€์žˆ์Šต๋‹ˆ๋‹ค. ๋˜ํ•œ, ์ผ๋ถ€ ์นธ์—๋Š” ํ•จ์ •์ด ์žˆ์œผ๋ฉฐ, ํ•ด๋‹น ์นธ์œผ๋กœ๋Š” ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

์ง„์ˆ˜๋Š” ์ฒ˜์Œ์— (1, 1) ์ขŒํ‘œ์—์„œ ์ถœ๋ฐœํ•ด ๋ณด๋ฌผ์ด ์žˆ๋Š” ์นธ์œผ๋กœ ์ด๋™ํ•˜๋ ค ํ•ฉ๋‹ˆ๋‹ค. ์ด๋™ํ•  ๋•Œ๋Š” [์ƒ,ํ•˜,์ขŒ,์šฐ]๋กœ ์ธ์ ‘ํ•œ ๋„ค ์นธ ์ค‘ ํ•œ ์นธ์œผ๋กœ ๊ฑธ์–ด์„œ ์ด๋™ํ•ฉ๋‹ˆ๋‹ค. ํ•œ ์นธ์„ ๊ฑธ์–ด์„œ ์ด๋™ํ•˜๋Š” ๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์€ 1์ž…๋‹ˆ๋‹ค.

์ง„์ˆ˜๋Š” ๋ณด๋ฌผ์ด ์œ„์น˜ํ•œ ์นธ์œผ๋กœ ์ˆ˜์›”ํ•˜๊ฒŒ ์ด๋™ํ•˜๊ธฐ ์œ„ํ•ด ์‹ ๋น„๋กœ์šด ์‹ ๋ฐœ์„ ํ•˜๋‚˜ ์ค€๋น„ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด ์‹ ๋ฐœ์„ ์‹ ๊ณ  ๋›ฐ๋ฉด ํ•œ ๋ฒˆ์— ๋‘ ์นธ์„ ์ด๋™ํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ํ•จ์ •์ด ์žˆ๋Š” ์นธ๋„ ๋„˜์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ, ์ด ์‹ ๋ฐœ์€ ํ•œ ๋ฒˆ๋ฐ–์— ์‚ฌ์šฉํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ์‹ ๋น„๋กœ์šด ์‹ ๋ฐœ์„ ์‚ฌ์šฉํ•˜์—ฌ ๋›ฐ์–ด์„œ ๋‘ ์นธ์„ ์ด๋™ํ•˜๋Š” ์‹œ๊ฐ„๋„ 1์ž…๋‹ˆ๋‹ค.

์ด๋•Œ ์ง„์ˆ˜๊ฐ€ ์ถœ๋ฐœ์ ์—์„œ ๋ณด๋ฌผ์ด ์œ„์น˜ํ•œ ์นธ์œผ๋กœ ์ด๋™ํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์ตœ์†Œ ์‹œ๊ฐ„์„ ๊ตฌํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์ง„์ˆ˜์˜ ๋ณด๋ฌผ์ง€๋„๊ฐ€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์„ ๋•Œ, ์ง„์ˆ˜๊ฐ€ ๊ฑธ์–ด์„œ ์˜ค๋ฅธ์ชฝ์œผ๋กœ 3์นธ, ๊ฑธ์–ด์„œ ์œ„์ชฝ์œผ๋กœ 3์นธ ์ด๋™ํ•˜๋ฉด 6์˜ ์‹œ๊ฐ„์— ๋ณด๋ฌผ์ด ์œ„์น˜ํ•œ ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ, ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๊ฑธ์–ด์„œ 1์นธ, ์œ„์ชฝ์œผ๋กœ ๊ฑธ์–ด์„œ 1์นธ, ์‹ ๋น„๋กœ์šด ์‹ ๋ฐœ์„ ์‚ฌ์šฉํ•˜์—ฌ ์œ„๋กœ ๋›ฐ์–ด 2์นธ, ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๊ฑธ์–ด์„œ 2์นธ ์ด๋™ํ•œ๋‹ค๋ฉด ์ด 5์˜ ์‹œ๊ฐ„์— ๋ณด๋ฌผ์ด ์œ„์น˜ํ•œ ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ด๋ณด๋‹ค ๋น ๋ฅธ ์‹œ๊ฐ„ ๋‚ด์— ๋ณด๋ฌผ์ด ์žˆ๋Š” ์œ„์น˜์— ๋„์ฐฉํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

์ง„์ˆ˜์˜ ๋ณด๋ฌผ์ง€๋„๊ฐ€ ํ‘œํ˜„ํ•˜๋Š” ์ง€์—ญ์˜ ๊ฐ€๋กœ ๊ธธ์ด๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ n, ์„ธ๋กœ ๊ธธ์ด๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ m, ํ•จ์ •์˜ ์œ„์น˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” 2์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด hole์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ง„์ˆ˜๊ฐ€ ๋ณด๋ฌผ์ด ์žˆ๋Š” ์นธ์œผ๋กœ ์ด๋™ํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์ตœ์†Œ ์‹œ๊ฐ„์„ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”. ๋‹จ, ๋ณด๋ฌผ์ด ์žˆ๋Š” ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์—†๋‹ค๋ฉด, -1์„ return ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์ œํ•œ ์‚ฌํ•ญ

  • 1 ≤ n, m ≤ 1,000
    • ๋‹จ, n * m์ด 3 ์ด์ƒ์ธ ๊ฒฝ์šฐ๋งŒ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
  • 1 ≤ hole์˜ ๊ธธ์ด ≤ n * m - 2
    • hole[i]๋Š” [a, b]์˜ ํ˜•ํƒœ์ด๋ฉฐ, (a, b) ์นธ์— ํ•จ์ •์ด ์กด์žฌํ•œ๋‹ค๋Š” ์˜๋ฏธ์ด๋ฉฐ, 1 ≤ a ≤ n, 1 ≤ b ≤ m์„ ๋งŒ์กฑํ•ฉ๋‹ˆ๋‹ค.
    • ๊ฐ™์€ ํ•จ์ •์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ์ค‘๋ณตํ•ด์„œ ๋“ค์–ด์žˆ์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • (1, 1) ์นธ๊ณผ (n, m) ์นธ์€ ํ•ญ์ƒ ํ•จ์ •์ด ์—†์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

n m hole result
4 4 [[2, 3], [3, 3]] 5
5 4 [[1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 3], [4, 1], [4, 3], [5, 3]] -1

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

  • ๋ณธ๋ฌธ์˜ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

  • ๋ณด๋ฌผ์ง€๋„๋ฅผ ๊ทธ๋ฆผ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด ์•„๋ž˜์™€ ๊ฐ™์œผ๋ฉฐ, ๋ณด๋ฌผ์ด ์œ„์น˜ํ•œ ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ, -1์„ return ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

ํ’€์ด

  • ๋‹จ์ˆœ ๊ธธ์ฐพ๊ธฐ ๋ฌธ์ œ๋ผ๊ณ  ์ƒ๊ฐํ–ˆ์ง€๋งŒ ๋งˆ๋ฒ•์˜ ์‹ ๋ฐœ์ด ์กด์žฌํ•œ๋‹ค.
    • ๊ทธ๋ž˜์„œ BFS๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์— ๋ช‡๋ฒˆ์งธ ๋‹จ๊ณ„์ธ์ง€ ์ ๊ณ , ๊ทธ ์ˆ˜์˜ ์ฐจ์ด๊ฐ€ ํฐ ๊ณณ์—์„œ ์ ํ”„ํ•˜๋ฉด ๋œ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋Š”๋ฐ, ์•„ํ•˜ํ•˜ํ•˜ ๊ทธ๋ ‡๊ฒŒ ์‰ฝ๊ฒŒ ๋ ๋ฆฌ๊ฐ€ ์—†์ง€.
    • ์ž…์ถœ๋ ฅ ์˜ˆ#2์—์„œ ์‚ฌ๋ฐฉ์ด ๋ง‰ํžŒ ๊ณณ์—์„œ ์‹œ์ž‘ํ•ด๋ฒ„๋ฆฌ๋ฉด, ๋งˆ๋ฒ•์‹ ๋ฐœ๋„ ์ด๋™ ๋ฐฉ์‹์— ์ถ”๊ฐ€ํ•ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒฐ๋ก .
    • ์ฆ‰, ๊ธฐ์กด ๊ธธ์ฐพ๊ธฐ ๋ฐฉ์‹์— ํ•จ์ •(๋ฒฝ)์ด ์žˆ๊ณ , ๋ฒฝ์€ ๋งˆ๋ฒ•์‹ ๋ฐœ๋กœ 1ํšŒ ๋„˜์„ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ทœ์น™๊นŒ์ง€ ์ ์šฉํ•ด์„œ BFS๋ฅผ ํ•ด์•ผํ•œ๋‹ค.
    • ๊ธฐ๋ณธ์ ์œผ๋กœ๋Š” ํ•จ์ •์„ ๋›ฐ์–ด๋„˜์–ด์„œ ๋” ๋นจ๋ฆฌ๊ฐ€๋Š” ๊ฒƒ์ด ์ข‹๊ณ , ํ•จ์ •์ด ์—†์œผ๋ฉด ์•„๋ฌด๋Œ€์„œ๋‚˜ ๋›ฐ์–ด์„œ 1์นธ ๋นจ๋ฆฌ ๊ฐ€๋Š”๊ฒŒ ์ข‹๋‹ค. ๊ทผ๋ฐ ๊ทธ๋ ‡๊ฒŒ ๋˜๋ฉด DP+BFS์ธ๊ฐ€?
728x90
๋ฐ˜์‘ํ˜•