๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Programming/Algorithm

[Python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋ฌด์ธ๋„ ์—ฌํ–‰ ํŒŒ์ด์ฌ ํ’€์ด

728x90
๋ฐ˜์‘ํ˜•
import sys

sys.setrecursionlimit(10000)

def dfs(x, y, maps, visit):
    val = 0

    if x < 0 or x >= len(maps[0]): return val
    if y < 0 or y >= len(maps): return val
    if visit[y][x] is True: return val
    if maps[y][x] == "X": return val

    visit[y][x] = True
    return int(maps[y][x]) + dfs(x - 1 , y, maps, visit) + dfs(x + 1 , y, maps, visit) + dfs(x, y - 1, maps, visit) + dfs(x, y + 1, maps, visit)

def solution(maps):
    answer = []
    ylen = len(maps)
    xlen = len(maps[0])
    visit = [[False] * xlen for _ in range(ylen)]

    for x in range(xlen):
        for y in range(ylen):
            if maps[y][x] == "X": continue
            if visit[y][x] is True: continue

            cs = dfs(x, y, maps, visit)

            if cs > 0: answer.append(cs)
    if len(answer) == 0: answer.append(-1)
    else: answer.sort()

    return answer

๋ฌธ์ œ๋Š” ์ƒ๋žต...

 

ํŠน์ • ์ง€์ ์—์„œ ๋ชจ๋“  ์—ฐ๊ฒฐ์ ์„ ํ™•์ธํ•˜๊ณ  ์—ฐ๊ฒฐ๋œ ์ ๋“ค๋ผ๋ฆฌ ๊ฐ’์˜ ์ดํ•ฉ์„ ์ฐพ๋Š” ๋ฌธ์ œ

๋ชจ๋“  ์—ฐ๊ฒฐ์  -> ๋ชจ๋“  ์ง€์ ์„ ํ™•์ธํ•˜๋Š” ์™„์ „ํƒ์ƒ‰ -> dfs or bfs๋ฅผ ์„ ํƒ

๋ฌธ์ œ ์ œํ•œ ์กฐ๊ฑด์—์„œ ํ–‰๊ณผ ์—ด์˜ ์ตœ๋Œ€ 100์ด์—ˆ๊ธฐ์— O(n^2) ์ตœ์•…์˜ ๊ฒฝ์šฐ 10000 ์ดํ•˜์˜ ๋…ธ๋“œ๋ฅผ ํ™•์ธํ•˜๋ฏ€๋กœ ์™„์ „ ํƒ์ƒ‰ ๊ฐ€๋Šฅํ•˜๋‹ค.

 

๊ณ ๋ ค์‚ฌํ•ญ

1. ๋ฌธ์ œ์˜ ์กฐ๊ฑด์ธ 'X' ๊ฐ’์ด๋ผ๋ฉด ๊ฑด๋„ˆ ๋œ€.

2. ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ์ ์ด ์žˆ๋‹ค๋ฉด(visit array ๊ฐ€ true ๋ผ๋ฉด) ๊ฑด๋„ˆ ๋œ€.

3. ์กฐ๊ฑด์˜ ์˜์—ญ์„ ๋ฒ—์–ด๋‚œ๋‹ค๋ฉด ๊ฑด๋„ˆ ๋œ€.

4. dfs ์„ ํƒ ์‹œ ์ตœ๋Œ€ ๊นŠ์ด 10000๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ์ตœ์†Œ recursionlimit์€ 10000 ์ด์ƒ์„ ํ•ด์คŒ(ํŒŒ์ด์ฌ์˜ ๊ฒฝ์šฐ).

5. ํ˜„ ์ง€์ ์—์„œ 4๋ฐฉํ–ฅ์„ ๋ชจ๋‘ ํ™•์ธํ•˜๊ณ  ์ถ”๊ฐ€์ ์œผ๋กœ ๋ด์•ผํ•  ์ง€์ ์ด ์กด์žฌํ•œ๋‹ค๋ฉด ์žฌ๊ท€์ ์œผ๋กœ ํ™•์ธํ•˜๋ฉฐ ๊ฐ’์„ ๋ˆ„์ ํ•ด์คŒ.

6. ์กฐ๊ฑด์— ์ผ์น˜ํ•˜๋Š” ๊ฒƒ์ด ์•„๋ฌด๊ฒƒ๋„ ์—†์„ ๊ฒฝ์šฐ answer์— -1์„ ๋„ฃ์–ด์คŒ.

7. ์กฐ๊ฑด์— ์ผ์น˜ํ•˜๋Š” ๊ฒƒ์ด ํ•˜๋‚˜ ์ด์ƒ์ผ ๊ฒฝ์šฐ, ์ˆซ์ž์˜ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด์คŒ.

 

์ด๋Ÿฐ ์™„์ „ํƒ์ƒ‰์˜ ๊ฒฝ์šฐ, ๋‚˜ ์ฒ˜๋Ÿผ ๋ฐฉ๋ฌธ ๋…ธ๋“œ๋ฅผ ํ™•์ธํ•˜๋Š” visit ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•˜์ง€ ์•Š๊ณ  maps์˜ ๊ฐ’์„ ์Œ์ˆ˜ํ™” ์‹œ์ผœ์„œ ํ™•์ธํ•œ๋‹ค๋˜์ง€ ํ•˜๋Š” ๊ธฐ๋ฒ•์„ ํ™œ์šฉํ•  ์ˆ˜๋„ ์žˆ๋‹ค.

ํ•˜์ง€๋งŒ, ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์™„์ „ํžˆ ์ต์ˆ™ํ•œ ์‚ฌ๋žŒ์ด ์•„๋‹ˆ๋ผ๋ฉด, ์กฐ๊ธˆ ๋” ์ง๊ด€์ ์œผ๋กœ ์•Œ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ด ์ข‹๋‹ค๊ณ  ์ƒ๊ฐํ•œ๋‹ค.(์ฃผ๊ด€์ )

(๊ธฐ์—… ์ฝ”ํ…Œ์—์„œ๋Š” ๋ฉ”๋ชจ๋ฆฌ๋Š” ํฌ๊ฒŒ ๋ฌธ์ œ๊ฐ€ ๋˜์ง€ ์•Š๋Š”๋‹ค.)

 

๊ฒฐ๋ก .

๋ฌธ์ œ๋ฅผ ๋ณด๊ณ  ๋ฐ”๋กœ ํ’€์ด๋ฐฉ๋ฒ•์„ ์ฐพ์•„๋ƒˆ์ง€๋งŒ, ์˜ค๋žœ๋งŒ์— ํ’€์ด๋ผ์„œ ์ƒ๊ฐ๋ณด๋‹ค ๋ฒ„๋ฒ…์˜€๋‹ค.

์‚ฌ์‹ค maps, visit์˜ ๋…ธ๋“œ ๋ฐฉ๋ฌธ์‹œ ํ–‰ ์—ด(x์™€ y)๋ฅผ ๊ฑฐ๊พธ๋กœ ์ž…๋ ฅํ–ˆ๋Š”๋ฐ ์ฐพ๋Š”๋ฐ ์‹œ๊ฐ„์ด ๊ฑธ๋ ธ๋‹ค... ๊ฐ์ด ๋งŽ์ด ๋–จ์–ด์ ธ์žˆ๋‹ค...

๋†’์€ ๋‚œ์ด๋„๊ฐ€ ์•„๋‹ˆ๋ผ๋„ ํ•˜๋ฃจ์— ํ•œ ๋ฌธ์ œ์”ฉ์ด๋ผ๋„ ๊พธ์ค€ํžˆ ํ’€์–ด๋ด์•ผ๊ฒ ๋‹ค.

728x90
๋ฐ˜์‘ํ˜•