[programmers] ๋“ฑ๊ตฃ๊ธธ - Java

ํญ์šฐ๋กœ ๋ฌผ์— ์ž ๊ธด ์ง€์—ญ์„ ํ”ผํ•˜์—ฌ ํ•™๊ต์— ๊ฐ€๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋กœ, ์ฃผ์–ด์ง„ ๊ฒฉ์ž์—์„œ ์˜ค๋ฅธ์ชฝ๊ณผ ์•„๋ž˜์ชฝ์œผ๋กœ๋งŒ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค. ๋™์  ๊ณ„ํš๋ฒ•์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ฒฝ๋กœ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๋ฉฐ, ๋ฌผ์— ์ž ๊ธด ์ง€์—ญ์€ -1๋กœ ํ‘œ์‹œํ•˜์—ฌ ๊ฒฝ๋กœ ๊ณ„์‚ฐ์—์„œ ์ œ์™ธํ•œ๋‹ค. ์ตœ์ข… ๊ฒฐ๊ณผ๋Š” ๊ฒฉ์ž์˜ ์˜ค๋ฅธ์ชฝ ํ•˜๋‹จ ๋ชจ์„œ๋ฆฌ์— ์œ„์น˜ํ•œ ๊ฐ’์œผ๋กœ, ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(mร—n)์ด๋‹ค.
DriedPollack's avatar
Oct 29, 2024
[programmers] ๋“ฑ๊ตฃ๊ธธ - Java

๋“ฑ๊ตฃ๊ธธ

๋ฌธ์ œ ์„ค๋ช…

๊ณ„์†๋˜๋Š” ํญ์šฐ๋กœ ์ผ๋ถ€ ์ง€์—ญ์ด ๋ฌผ์— ์ž ๊ฒผ์Šต๋‹ˆ๋‹ค. ๋ฌผ์— ์ž ๊ธฐ์ง€ ์•Š์€ ์ง€์—ญ์„ ํ†ตํ•ด ํ•™๊ต๋ฅผ ๊ฐ€๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ง‘์—์„œ ํ•™๊ต๊นŒ์ง€ ๊ฐ€๋Š” ๊ธธ์€ m x n ํฌ๊ธฐ์˜ ๊ฒฉ์ž๋ชจ์–‘์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
์•„๋ž˜ ๊ทธ๋ฆผ์€ m = 4, n = 3 ์ธ ๊ฒฝ์šฐ์ž…๋‹ˆ๋‹ค.
notion image
๊ฐ€์žฅ ์™ผ์ชฝ ์œ„, ์ฆ‰ ์ง‘์ด ์žˆ๋Š” ๊ณณ์˜ ์ขŒํ‘œ๋Š” (1, 1)๋กœ ๋‚˜ํƒ€๋‚ด๊ณ  ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜, ์ฆ‰ ํ•™๊ต๊ฐ€ ์žˆ๋Š” ๊ณณ์˜ ์ขŒํ‘œ๋Š” (m, n)์œผ๋กœ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
๊ฒฉ์ž์˜ ํฌ๊ธฐ m, n๊ณผ ๋ฌผ์ด ์ž ๊ธด ์ง€์—ญ์˜ ์ขŒํ‘œ๋ฅผ ๋‹ด์€ 2์ฐจ์› ๋ฐฐ์—ด puddles์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์˜ค๋ฅธ์ชฝ๊ณผ ์•„๋ž˜์ชฝ์œผ๋กœ๋งŒ ์›€์ง์—ฌ ์ง‘์—์„œ ํ•™๊ต๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋‹จ๊ฒฝ๋กœ์˜ ๊ฐœ์ˆ˜๋ฅผ 1,000,000,007๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • ๊ฒฉ์ž์˜ ํฌ๊ธฐ m, n์€ 1 ์ด์ƒ 100 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
    • m๊ณผ n์ด ๋ชจ๋‘ 1์ธ ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • ๋ฌผ์— ์ž ๊ธด ์ง€์—ญ์€ 0๊ฐœ ์ด์ƒ 10๊ฐœ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ์ง‘๊ณผ ํ•™๊ต๊ฐ€ ๋ฌผ์— ์ž ๊ธด ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

m
n
puddles
return
4
3
[[2, 2]]
4

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

notion image

solution.java

class Solution { public int solution(int m, int n, int[][] puddles) { // ์ƒ์ˆ˜ ์ •์˜ final int MOD = 1_000_000_007; // ๊ฒฉ์ž ์ดˆ๊ธฐํ™” int[][] dp = new int[m + 1][n + 1]; // ๋ฌผ์— ์ž ๊ธด ์ง€์—ญ์„ -1๋กœ ํ‘œ์‹œ for (int[] puddle : puddles) { dp[puddle[0]][puddle[1]] = -1; } // (1,1)๋ถ€ํ„ฐ ๊ฒฉ์ž ์‹œ์ž‘ dp[1][1] = 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // ์‹œ์ž‘ ์…€๊ณผ ๋ฌผ์— ์ž ๊ธด ์ง€์—ญ ๊ฑด๋„ˆ๋›ฐ๊ธฐ if ((i == 1 && j == 1) || dp[i][j] == -1) continue; // ํ˜„์žฌ ์…€์— ๋Œ€ํ•œ ๋ฐฉ๋ฒ• ์ˆ˜ ๊ณ„์‚ฐ int fromAbove = (i > 1 && dp[i - 1][j] != -1) ? dp[i - 1][j] : 0; int fromLeft = (j > 1 && dp[i][j - 1] != -1) ? dp[i][j - 1] : 0; dp[i][j] = (fromAbove + fromLeft) % MOD; System.out.println("dp["+i+"]["+j+"] = "+dp[i][j]); } } // ๊ฒฐ๊ณผ๋Š” ๊ฒฉ์ž์˜ ์˜ค๋ฅธ์ชฝ ํ•˜๋‹จ ๋ชจ์„œ๋ฆฌ์— ์žˆ๋Š” ๊ฐ’ return dp[m][n]; } }
 

ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ

  • ์˜ค๋ฅธ์ชฝ๊ณผ ์•„๋ž˜์ชฝ์œผ๋กœ๋งŒ ์›€์ง์ผ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ์ขŒ์ธก ์…€์—์„œ์˜ ๊ฐ€๋Šฅํ•œ ๊ฒฝ๋กœ ๊ฐœ์ˆ˜์™€ ์œ„์ชฝ ์…€์—์„œ์˜ ๊ฐ€๋Šฅํ•œ ๊ฒฝ๋กœ ๊ฐœ์ˆ˜๋ฅผ ํ•ฉ์น˜๋ฉด ํ˜„์žฌ ์…€์˜ ๊ฒฝ๋กœ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ์ด ๊ฒฝ์šฐ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” ๊ฐ ์…€์„ ํ•œ๋ฒˆ์”ฉ ๋ฐ˜๋ณตํ•˜๋ฏ€๋กœ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.
 

๊ฒฐ๋ก !

๋™์  ๊ณ„ํš๋ฒ•์„ ์‘์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๊ณ ๋ฏผํ•ด๋ณผ ์ˆ˜ ์žˆ์–ด์„œ ์ข‹์•˜๋‹ค.
 
Share article

More articles

See more posts

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ปDriedPollack's Blog