๋ฐ์ํ
๋ฌธ์
ํ์ด
DFS๋ก ๋ฐ์ด๋ฌ์ค ํผ์ง๊ฒ ํ๋ ํจ์์ ํ์ฌ ๋งต์์ ์์ ์์ญ์ ๊ตฌํ๋ ํจ์๋ฅผ ๋ง๋ค์ด ๋๊ณ ,
๋น ๊ณต๊ฐ์ ์ธํ๋ฆฌ๋ฅผ ์น๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ DFS๋ก ์ฐพ์ผ๋ฉด์ ๋งค๋ฒ ์์ ์์ญ์ ํฌ๊ธฐ๋ฅผ ๊ฒ์ฌํ๋ค.
์ฝ๋
n, m = map(int,input().split())
data = [] # ์ด๊ธฐ ๋งต ๋ฆฌ์คํธ
temp = [[0]*m for _ in range(n)]
for _ in range(n):
data.append(list(map(int,input().split())))
# ์๋จ๋๋ถ
dx = [-1,0,1,0]
dy = [0,1,0,-1]
result = 0
# DFS๋ก ๋ฐ์ด๋ฌ์ค ํผ์ง๊ฒ ํ๊ธฐ
def virus(x,y):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# ์ํ์ข์ฐ ์ค์์ ๋ฐ์ด๋ฌ์ค๊ฐ ํผ์ง ์ ์๋ ๊ฒฝ์ฐ
if nx >= 0 and nx < n and ny >=0 and ny < m :
if temp[nx][ny] == 0:
# ํด๋น ์์น์ ๋ฐ์ด๋ฌ์ค ๋ฐฐ์นํ๊ณ , ์ฌ๊ท์ ์ผ๋ก ์ํ
temp[nx][ny] = 2
virus(nx,ny)
# ํ์ฌ ๋งต์์ ์์ ์์ญ์ ํฌ๊ธฐ ๊ณ์ฐ
def get_score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j] == 0:
score += 1
return score
# DFS๋ฅผ ์ด์ฉํ์ฌ ์ธํ๋ฆฌ๋ฅผ ์ค์นํ๋ฉด์, ๋งค๋ฒ ์์ ์์ญ์ ํฌ๊ธฐ ๊ณ์ฐ
def main_dfs(count):
global result
# ์ธํ๋ฆฌ๊ฐ 3๊ฐ ์ค์น๋ ๊ฒฝ์ฐ
if count ==3:
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
# ๊ฐ ๋ฐ์ด๋ฌ์ค์ ์์น์์ ์ ํ ์งํ
for i in range(n):
for j in range(m):
if temp[i][j] == 2:
virus(i,j)
# ์์ ์์ญ์ ์ต๋๊ฐ ๊ณ์ฐ
result = max(result, get_score())
return
# ๋น ๊ณต๊ฐ์ ์ธํ๋ฆฌ ์ค์น -> ์ธํ๋ฆฌ ์ค์น๋ ๋น๊ณต๊ฐ์ด n๊ฐ ์ผ๋, nC3 ๊ฐ์ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ชจ๋ ๊ฒํ ํด์ผํจ / 0์ธ ์ขํ๋ฅผ ๋ชจ๋ ๊ตฌํ๊ณ ๋ชจ๋ combination์ ๊ตฌํด์ ํด๋ ๋ ๋ฏ
# i,j ์ํํ๋ฉด์ ์ฒซ ๋ฒฝ์ธ์ฐ๊ณ , dfs ํ๊ณ i,j ์ํํ๋ฉด์ 2๋ฒ์งธ ๋ฒฝ ์ธ์ฐ๊ณ ๋ค์ dfsํ๊ณ
# 3๋ฒ ์งธ ๋ฒฝ ์ธ์ฐ๊ณ get_score() ์์ ์ง์ญ ๊ณ์ฐํ๊ณ , ์ฌ๊ท ํ๋ฆฌ๋ฉด์ 3๋ฒ์งธ ๋ฒฝ ์ง์ฐ๊ณ ๋ค์ ์์น์
# 3๋ฒ ์งธ ๋ฒฝ ๋ค์ ์ธ์ฐ๊ณ ... ๊ณ์ ๋ฐ๋ณตํ๋ฉด ๋ฒฝ์ ์ธ์ธ ์ ์๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์ ๋ค ํ์ธ
for i in range(n):
for j in range(m):
if data[i][j] == 0: # ๋น ๊ณต๊ฐ ์ผ ๋
data[i][j] = 1 # ๋ฒฝ ์ธ์ฐ๊ณ
count += 1 # ๋ฒฝ ์ธ์ธ ๋ ๋ง๋ค count +=1
main_dfs(count) # ๋ค์ ๋ฒฝ ์ธ์ฐ๊ธฐ ์ํด dfs
data[i][j] = 0 # ์ฌ๊ท ํ๋ฆฌ๋ ๊ณผ์ ์ธ์ ๋ ๋ฒฝ ์ง์ฐ๊ณ
count -= 1 # ์นด์ดํธ๋ ๋ณต๊ท
main_dfs(0)
print(result)
๋ฐ์ํ
'๐ป Programming > ์๊ณ ๋ฆฌ์ฆ ํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[python] ํ๋ก๊ทธ๋๋จธ์ค_๋คํธ์ํฌ (DFS&BFS) (0) | 2022.02.06 |
---|---|
[python] ๋ฐฑ์ค18405_๊ฒฝ์์ ์ ์ผ (DFS&BFS) (0) | 2022.02.06 |
[python] ๋ฐฑ์ค18352_ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ (DFS&BFS) (0) | 2022.02.06 |
[ํ๋ก๊ทธ๋๋จธ์ค] 'ํ์ด์ฌ์ ํ์ด์ฌ๋ต๊ฒ' ๊ฐ์ ์ ๋ฆฌ (0) | 2021.08.03 |
[BFS] ๋ฏธ๋ก ํ์ถ (0) | 2021.05.17 |