deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

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

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

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

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim

๋งž์™œํ‹€

[python] ๋ฐฑ์ค€ - 3055. ํƒˆ์ถœ
Algorithm Problem/Python

[python] ๋ฐฑ์ค€ - 3055. ํƒˆ์ถœ

2020. 9. 23. 20:25
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

  • G5 | BFS, ๊ทธ๋ž˜ํ”„?

๋‹จ์ˆœํžˆ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๋Š” ๊ฒƒ๊ณผ ๋‹ฌ๋ฆฌ ๋งต์ด ๊ณ„์† ๋ณ€ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

๋กœ์ง์€ ๊ฐ„๋‹จํ•˜๋‹ค.

  • ๊ณ ์Šด๋„์น˜๋ฅผ ์ƒํ•˜์ขŒ์šฐ๋กœ ์ด๋™์‹œํ‚จ๋‹ค.
  • ๋ฌผ๋„ ์ƒํ•˜์ขŒ์šฐ๋กœ ํ˜๋Ÿฌ๋„˜์นœ๋‹ค.
  • ๋‹ค์‹œ ๊ณ ์Šด๋„์น˜๋ฅผ ์ƒํ•˜์ขŒ์šฐ๋กœ ์ด๋™์‹œํ‚จ๋‹ค. (ํ•˜์ง€๋งŒ ๋ฌผ์— ์ž ๊ฒจ์žˆ๋Š” ๊ณ ์Šด๋„์น˜๋Š” ์ด๋™ํ•  ์ˆ˜ ์—†๋‹ค)
  • ๋‹ค์‹œ ๋ฌผ์„ ์ƒํ•˜์ขŒ์šฐ๋กœ ํ˜๋Ÿฌ๋„˜์น˜๊ฒŒํ•œ๋‹ค.
  • ์œ„์˜ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜๋ฉด์„œ ๊ณ ์Šด๋„์น˜๊ฐ€ ๊ตด์— ๋„์ฐฉํ•˜๋ฉด ๋

๐Ÿ’จ

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

def flood(w):
    new_water = []
    for x, y in w:
        for k in range(len(dx)):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if forest[nx][ny] == '.' or type(forest[nx][ny]) == int:
                    forest[nx][ny] = '*'
                    new_water.append((nx, ny))
    return new_water


def move_hedgehog(h):
    new_hedgehog = []
    for x, y in h:
        if forest[x][y] != '*':
            for k in range(len(dx)):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < R and 0 <= ny < C:
                    if forest[nx][ny] == 'D':
                        forest[nx][ny] = forest[x][y] + 1
                        return 'finish'
                    if forest[nx][ny] == '.':
                        forest[nx][ny] = forest[x][y] + 1
                        new_hedgehog.append((nx, ny))
    return new_hedgehog


dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
if __name__ == '__main__':
    R, C = map(int, input().split())
    forest = [list(input()) for _ in range(R)]

    water = []
    hedgehog = []
    cave = []
    for i in range(R):
        for j in range(C):
            if forest[i][j] == '*':
                water.append((i, j))
            elif forest[i][j] == 'S':
                forest[i][j] = 0
                hedgehog.append((i, j))
            elif forest[i][j] == 'D':
                cave = [i, j]

    while hedgehog:
        hedgehog = move_hedgehog(hedgehog)
        if hedgehog == 'finish':
            print(forest[cave[0]][cave[1]])
            break
        water = flood(water)
    else:
        print('KAKTUS')

๐Ÿ“•๋ฌธ์ œ ํ™•์ธ

์ถœ์ฒ˜: BACKJOON ONLINE JUDGE

๋งํฌ: https://www.acmicpc.net/problem/3055

 

3055๋ฒˆ: ํƒˆ์ถœ

์‚ฌ์•…ํ•œ ์•”ํ‘์˜ ๊ตฐ์ฃผ ์ด๋ฏผํ˜์€ ๋“œ๋””์–ด ๋งˆ๋ฒ• ๊ตฌ์Šฌ์„ ์†์— ๋„ฃ์—ˆ๊ณ , ๊ทธ ๋Šฅ๋ ฅ์„ ์‹คํ—˜ํ•ด๋ณด๊ธฐ ์œ„ํ•ด ๊ทผ์ฒ˜์˜ ํ‹ฐ๋–ฑ์ˆฒ์— ํ™์ˆ˜๋ฅผ ์ผ์œผํ‚ค๋ ค๊ณ  ํ•œ๋‹ค. ์ด ์ˆฒ์—๋Š” ๊ณ ์Šด๋„์น˜๊ฐ€ ํ•œ ๋งˆ๋ฆฌ ์‚ด๊ณ  ์žˆ๋‹ค. ๊ณ ์Šด๋„์น˜๋Š” ์ œ๏ฟฝ๏ฟฝ

www.acmicpc.net


๋ฌธ์ œ

์‚ฌ์•…ํ•œ ์•”ํ‘์˜ ๊ตฐ์ฃผ ์ด๋ฏผํ˜์€ ๋“œ๋””์–ด ๋งˆ๋ฒ• ๊ตฌ์Šฌ์„ ์†์— ๋„ฃ์—ˆ๊ณ , ๊ทธ ๋Šฅ๋ ฅ์„ ์‹คํ—˜ํ•ด๋ณด๊ธฐ ์œ„ํ•ด ๊ทผ์ฒ˜์˜ ํ‹ฐ๋–ฑ์ˆฒ์— ํ™์ˆ˜๋ฅผ ์ผ์œผํ‚ค๋ ค๊ณ  ํ•œ๋‹ค. ์ด ์ˆฒ์—๋Š” ๊ณ ์Šด๋„์น˜๊ฐ€ ํ•œ ๋งˆ๋ฆฌ ์‚ด๊ณ  ์žˆ๋‹ค. ๊ณ ์Šด๋„์น˜๋Š” ์ œ์ผ ์นœํ•œ ์นœ๊ตฌ์ธ ๋น„๋ฒ„์˜ ๊ตด๋กœ ๊ฐ€๋Šฅํ•œ ๋นจ๋ฆฌ ๋„๋ง๊ฐ€ ํ™์ˆ˜๋ฅผ ํ”ผํ•˜๋ ค๊ณ  ํ•œ๋‹ค.

ํ‹ฐ๋–ฑ์ˆฒ์˜ ์ง€๋„๋Š” Rํ–‰ C์—ด๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๋น„์–ด์žˆ๋Š” ๊ณณ์€ '.'๋กœ ํ‘œ์‹œ๋˜์–ด ์žˆ๊ณ , ๋ฌผ์ด ์ฐจ์žˆ๋Š” ์ง€์—ญ์€ '*', ๋Œ์€ 'X'๋กœ ํ‘œ์‹œ๋˜์–ด ์žˆ๋‹ค. ๋น„๋ฒ„์˜ ๊ตด์€ 'D'๋กœ, ๊ณ ์Šด๋„์น˜์˜ ์œ„์น˜๋Š” 'S'๋กœ ๋‚˜ํƒ€๋‚ด์–ด์ ธ ์žˆ๋‹ค.

๋งค ๋ถ„๋งˆ๋‹ค ๊ณ ์Šด๋„์น˜๋Š” ํ˜„์žฌ ์žˆ๋Š” ์นธ๊ณผ ์ธ์ ‘ํ•œ ๋„ค ์นธ ์ค‘ ํ•˜๋‚˜๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค. (์œ„, ์•„๋ž˜, ์˜ค๋ฅธ์ชฝ, ์™ผ์ชฝ) ๋ฌผ๋„ ๋งค ๋ถ„๋งˆ๋‹ค ๋น„์–ด์žˆ๋Š” ์นธ์œผ๋กœ ํ™•์žฅํ•œ๋‹ค. ๋ฌผ์ด ์žˆ๋Š” ์นธ๊ณผ ์ธ์ ‘ํ•ด์žˆ๋Š” ๋น„์–ด์žˆ๋Š” ์นธ(์ ์–ด๋„ ํ•œ ๋ณ€์„ ๊ณต์œ )์€ ๋ฌผ์ด ์ฐจ๊ฒŒ ๋œ๋‹ค. ๋ฌผ๊ณผ ๊ณ ์Šด๋„์น˜๋Š” ๋Œ์„ ํ†ต๊ณผํ•  ์ˆ˜ ์—†๋‹ค. ๋˜, ๊ณ ์Šด๋„์น˜๋Š” ๋ฌผ๋กœ ์ฐจ์žˆ๋Š” ๊ตฌ์—ญ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์—†๊ณ , ๋ฌผ๋„ ๋น„๋ฒ„์˜ ์†Œ๊ตด๋กœ ์ด๋™ํ•  ์ˆ˜ ์—†๋‹ค.

ํ‹ฐ๋–ฑ์ˆฒ์˜ ์ง€๋„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ณ ์Šด๋„์น˜๊ฐ€ ์•ˆ์ „ํ•˜๊ฒŒ ๋น„๋ฒ„์˜ ๊ตด๋กœ ์ด๋™ํ•˜๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ ์‹œ๊ฐ„์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

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

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— 50๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜ R๊ณผ C๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๋‹ค์Œ R๊ฐœ ์ค„์—๋Š” ํ‹ฐ๋–ฑ์ˆฒ์˜ ์ง€๋„๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ๋ฌธ์ œ์—์„œ ์„ค๋ช…ํ•œ ๋ฌธ์ž๋งŒ ์ฃผ์–ด์ง„๋‹ค. 'D'์™€ 'S'๋Š” ํ•˜๋‚˜์”ฉ๋งŒ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๊ณ ์Šด๋„์น˜๊ฐ€ ๋น„๋ฒ„์˜ ๊ตด๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ๋น ๋ฅธ ์‹œ๊ฐ„์„ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ, ์•ˆ์ „ํ•˜๊ฒŒ ๋น„๋ฒ„์˜ ๊ตด๋กœ ์ด๋™ํ•  ์ˆ˜ ์—†๋‹ค๋ฉด, "KAKTUS"๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Algorithm Problem > Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํ’์„  ํ„ฐํŠธ๋ฆฌ๊ธฐ(์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ ์‹œ์ฆŒ1)  (0) 2020.09.25
[python] ๋ฐฑ์ค€ - 5014. ์Šคํƒ€ํŠธ๋งํฌ  (0) 2020.09.24
[python] ๋ฐฑ์ค€ - 1916. ์ตœ์†Œ๋น„์šฉ ๊ตฌํ•˜๊ธฐ  (0) 2020.09.23
[python] ๋ฐฑ์ค€ - 2225. ํ•ฉ๋ถ„ํ•ด  (0) 2020.09.22
[python] ๋ฐฑ์ค€ - 9251. LCS  (0) 2020.09.22
    'Algorithm Problem/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํ’์„  ํ„ฐํŠธ๋ฆฌ๊ธฐ(์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ ์‹œ์ฆŒ1)
    • [python] ๋ฐฑ์ค€ - 5014. ์Šคํƒ€ํŠธ๋งํฌ
    • [python] ๋ฐฑ์ค€ - 1916. ์ตœ์†Œ๋น„์šฉ ๊ตฌํ•˜๊ธฐ
    • [python] ๋ฐฑ์ค€ - 2225. ํ•ฉ๋ถ„ํ•ด
    deo2kim
    deo2kim
    ์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

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