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)๋ฅผ ๊ฑฐ๊พธ๋ก ์ ๋ ฅํ๋๋ฐ ์ฐพ๋๋ฐ ์๊ฐ์ด ๊ฑธ๋ ธ๋ค... ๊ฐ์ด ๋ง์ด ๋จ์ด์ ธ์๋ค...
๋์ ๋์ด๋๊ฐ ์๋๋ผ๋ ํ๋ฃจ์ ํ ๋ฌธ์ ์ฉ์ด๋ผ๋ ๊พธ์คํ ํ์ด๋ด์ผ๊ฒ ๋ค.
'Programming > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm] Union - Find (Python ๊ตฌํ) (0) | 2022.05.10 |
---|---|
[Algorithm] ์ฌ๊ท๋ฅผ ํตํ ์์ด(permutation) ๊ตฌํ(+ python ๋ด์ฅ ํจ์ ์ด์ฉ) (0) | 2022.05.01 |
[Algorithm] ํ๋ก์ด๋ ์์ฌ(Floyd Warshall) ์๊ณ ๋ฆฌ์ฆ(ft.ํ์ด์ฌ) (1) | 2022.05.01 |
[Algoritm] ํ๋ ฌ ํ์ (Python ๊ตฌํ) (0) | 2022.04.23 |
[Algorithm] ์ต๋ ๊ณต์ฝ์, ์ต์ ๊ณต๋ฐฐ์ ๊ตฌํ๊ธฐ (0) | 2022.04.06 |