๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/7576)
<ํ ๋งํ >
๋ฌธ์
์ฒ ์์ ํ ๋งํ ๋์ฅ์์๋ ํ ๋งํ ๋ฅผ ๋ณด๊ดํ๋ ํฐ ์ฐฝ๊ณ ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ํ ๋งํ ๋ ์๋์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๊ฒฉ์ ๋ชจ์ ์์์ ์นธ์ ํ๋์ฉ ๋ฃ์ด์ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ค.
์ฐฝ๊ณ ์ ๋ณด๊ด๋๋ ํ ๋งํ ๋ค ์ค์๋ ์ ์ต์ ๊ฒ๋ ์์ง๋ง, ์์ง ์ต์ง ์์ ํ ๋งํ ๋ค๋ ์์ ์ ์๋ค. ๋ณด๊ด ํ ํ๋ฃจ๊ฐ ์ง๋๋ฉด, ์ต์ ํ ๋งํ ๋ค์ ์ธ์ ํ ๊ณณ์ ์๋ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ต์ ํ ๋งํ ์ ์ํฅ์ ๋ฐ์ ์ต๊ฒ ๋๋ค. ํ๋์ ํ ๋งํ ์ ์ธ์ ํ ๊ณณ์ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ๋ค ๋ค ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ฅผ ์๋ฏธํ๋ค. ๋๊ฐ์ ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ค์๊ฒ๋ ์ํฅ์ ์ฃผ์ง ๋ชปํ๋ฉฐ, ํ ๋งํ ๊ฐ ํผ์ ์ ์ ๋ก ์ต๋ ๊ฒฝ์ฐ๋ ์๋ค๊ณ ๊ฐ์ ํ๋ค. ์ฒ ์๋ ์ฐฝ๊ณ ์ ๋ณด๊ด๋ ํ ๋งํ ๋ค์ด ๋ฉฐ์น ์ด ์ง๋๋ฉด ๋ค ์ต๊ฒ ๋๋์ง, ๊ทธ ์ต์ ์ผ์๋ฅผ ์๊ณ ์ถ์ด ํ๋ค.
ํ ๋งํ ๋ฅผ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ ๊ฒฉ์๋ชจ์์ ์์๋ค์ ํฌ๊ธฐ์ ์ต์ ํ ๋งํ ๋ค๊ณผ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ๋ฉฐ์น ์ด ์ง๋๋ฉด ํ ๋งํ ๋ค์ด ๋ชจ๋ ์ต๋์ง, ๊ทธ ์ต์ ์ผ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ. ๋จ, ์์์ ์ผ๋ถ ์นธ์๋ ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ์๋ ์๋ค.
์ ๋ ฅ
์ฒซ ์ค์๋ ์์์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ๋ ์ ์ M, N์ด ์ฃผ์ด์ง๋ค. M์ ์์์ ๊ฐ๋ก ์นธ์ ์, N์ ์์์ ์ธ๋ก ์นธ์ ์๋ฅผ ๋ํ๋ธ๋ค. ๋จ, 2 ≤ M, N ≤ 1,000์ด๋ค. ๋์งธ ์ค๋ถํฐ๋ ํ๋์ ์์์ ์ ์ฅ๋ ํ ๋งํ ๋ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ์ฆ, ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ์์์ ๋ด๊ธด ํ ๋งํ ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ํ๋์ ์ค์๋ ์์ ๊ฐ๋ก์ค์ ๋ค์ด์๋ ํ ๋งํ ์ ์ํ๊ฐ M๊ฐ์ ์ ์๋ก ์ฃผ์ด์ง๋ค. ์ ์ 1์ ์ต์ ํ ๋งํ , ์ ์ 0์ ์ต์ง ์์ ํ ๋งํ , ์ ์ -1์ ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ์นธ์ ๋ํ๋ธ๋ค.
ํ ๋งํ ๊ฐ ํ๋ ์ด์ ์๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฌ๋ฌ๋ถ์ ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ ๋๊น์ง์ ์ต์ ๋ ์ง๋ฅผ ์ถ๋ ฅํด์ผ ํ๋ค. ๋ง์ฝ, ์ ์ฅ๋ ๋๋ถํฐ ๋ชจ๋ ํ ๋งํ ๊ฐ ์ต์ด์๋ ์ํ์ด๋ฉด 0์ ์ถ๋ ฅํด์ผ ํ๊ณ , ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ง๋ ๋ชปํ๋ ์ํฉ์ด๋ฉด -1์ ์ถ๋ ฅํด์ผ ํ๋ค.
๋ฌธ์ ํ์ด
- my solution
import sys
from collections import deque
def bfs(graph, queue, visited, depth):
dx=[-1,1,0,0] # ์ํ์ข์ฐ
dy=[0,0,-1,1]
while queue:
temp=queue.popleft()
for i in range(4):
x=temp[0]+dx[i]
y=temp[1]+dy[i]
if x>=0 and x<len(graph) and y>=0 and y<len(graph[0]): # ์์ ๋ฒ์์ ๋ ๋ค๋ฉด
if visited[x][y]==0: # ๋ฐฉ๋ฌธ x, ํ ๋งํ o, ์์ต์
queue.append([x,y])
visited[x][y]=1 # ๋ฐฉ๋ฌธ
depth[x][y]=depth[temp[0]][temp[1]]+1 # ์ผ์ ๊ตฌํ๊ธฐ
if __name__=='__main__':
m,n=map(int, sys.stdin.readline().split())
graph=[]
answer=0 # ์ต์ ๋ ์ง
for i in range(n):
temp=list(map(int ,sys.stdin.readline().split()))
graph.append(temp)
visited=[[0]*m for i in range(n)] # ๋ฐฉ๋ฌธ ์ฌ๋ถ
depth=[[0]*m for i in range(n)] # ์ต์ ์ผ์ ๊ตฌํ๊ธฐ
queue=deque([])
for i in range(n):
for j in range(m):
if visited[i][j]==0 and graph[i][j]==1: # ๋ฐฉ๋ฌธ x, ์ต์ ํ ๋งํ
queue.append([i,j])
visited[i][j]=1
if graph[i][j]==-1: # ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์
visited[i][j]=1
bfs(graph, queue, visited, depth)
flag=0
for i in range(n):
for j in range(m):
if visited[i][j]==0: # ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ง ๋ชปํ๋ ๊ฒฝ์ฐ
flag=1
break
else:
if answer<depth[i][j]: # ์ต์ ์ผ์ ๊ตฌํ๊ธฐ
answer=depth[i][j]
if flag==1:
print(-1)
else:
print(answer)
- bfs (ํ ๋งํ ์ ๋ณด, queue , ๋ฐฉ๋ฌธ ์ฌ๋ถ list, day)
: dx, dy = ์ํ์ข์ฐ ํ์
: queue๊ฐ ๋น ๋๊น์ง ๋ฐ๋ณต -> ์ ์ผ ์ฒ์ ๊ฐ์ pop -> ์ํ์ข์ฐ๋ฅผ ํ์ธํ์ฌ ํ ๋งํ ์์ ๋ฒ์์ ์ํ๋ฉด -> ์์ง ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด -> queue์ ์ถ๊ฐ, ๋ฐฉ๋ฌธ o, ์ด๋ํ ์์น์ depth = ํ์ฌ ์์น์ depth +1 - main
: m, n ์ ๋ ฅ
: ํ ๋งํ ์ ๋ณด ์ ๋ ฅ
: graph = ํ ๋งํ ์ ๋ณด
answer= ์ต์ ๋ ์ง
visited = ๋ฐฉ๋ฌธ ์ฌ๋ถ
depth = ์ต์ ์ผ์ ๊ตฌํ๊ธฐ ์ํ day ์ ์ฅ
: ํ ๋งํ ์ ๋ณด ์ ์ฒด๋ฅผ ํ์ํ์ฌ ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฉฐ ์ต์ ํ ๋งํ ๋ฅผ queue์ ์ถ๊ฐ ๋ฐ ๋ฐฉ๋ฌธ o
: ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ๊ณณ์ bfs ํจ์์์ ์ํฅ๋ฐ์ง ์๋๋ก visited๋ฅผ 1๋ก ์ค์
: bfs ํจ์ ํธ์ถ
: ๋ฐฉ๋ฌธ ์ฌ๋ถ list๋ฅผ ์ ์ฒด ํ์ํ์ฌ 0์ด ์กด์ฌํ๋ฉด = ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ง ๋ชปํ๋ ๊ฒฝ์ฐ -> -1 ์ถ๋ ฅ
0์ด ์๋ค๋ฉด depth ์ค์์ ๊ฐ์ฅ ํฐ ๊ฐ ์ฐพ์์ ์ถ๋ ฅ = ์ต์ ์ผ์
์ฒ์ ๊ณ ๋ฏผํ๋ ๊ฒ์ ์ ์ต์ ํ ๋งํ ์ ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ๊ฒ์ ๊ตฌ๋ถํ๋ ๋ฐฉ๋ฒ์ด์๋ค. ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ์นธ์ ๋๋ฌ์ธ์ฌ ์๋ ์ ์ต์ ํ ๋งํ ๋ ์ต์ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค. ๊ทธ๋์ ํ ๋งํ ์ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ํ์ธํ๋ visited๋ฅผ ๊ตฌํํ์๋ค. ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ์นธ์ ๋ฏธ๋ฆฌ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ o๋ก ๋ฐ๊ฟ bfs๋ฅผ ๋ ๋ ์ด๋ฏธ ๋ฐฉ๋ฌธํ ๊ฒ์ผ๋ก ํ์ธํ์ฌ ํ์์ ์ง์ฅ์ ์ฃผ์ง ์๊ฒ ๋๋ค.
๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฉฐ ์ต์ ํ ๋งํ ๋ฅผ queue์ ๋ฃ์ด์ฃผ์ด bfs ํ๋๋ก ํด์ฃผ์๋ค. bfs ํจ์๋ฅผ ํธ์ถํ์ฌ ํ์ฌ ๊ฐ์ ์ํ์ข์ฐ๋ฅผ ์ดํด๋ณด๋ฉฐ ์์ ๋ฒ์์ ๋ ๋ค๋ฉด queue์ ์ถ๊ฐ ๋ฐ ๋ฐฉ๋ฌธ o, depth๋ฅผ update ํด์ค๋ค.
bfs๊ฐ ๋๋ ๋ค์ visited๋ฅผ ์ ์ฒด ํ์ํ์ฌ 0์ด ์๋ค๋ฉด ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ง ๋ชปํ ๊ฒฝ์ฐ๋ผ๊ณ ํ์ฌ -1์ ์ถ๋ ฅํด์ค๋ค. ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์๋ค๋ฉด depth ์ค์์ ๊ฐ์ฅ ํฐ ๊ฐ์ด ์ต์ ์ผ์ ์ด๋ฏ๋ก ๊ทธ ๊ฐ์ ์ฐพ์ ์ถ๋ ฅํด์ค๋ค.
โ ์ฒ์์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ ์ด์ ๋ ๋ฌด์์ธ๊ฐ?
์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ ํ ์๊ฐํ ๊ฒ์ max์ count ๋๋ฌธ์ด๋ผ๊ณ ์๊ฐํ์๋ค. ์ฒ์ ์ฝ๋๋ visited์์ 0์ ๊ฐ์๋ฅผ ์ฐพ๋ ๊ฒ๊ณผ ์ต์ ์ผ์๋ฅผ ๊ตฌํ๊ธฐ ์ํ์ฌ depth์์ max๋ฅผ ์ฌ์ฉํ์๋ค. ๊ทธ๋์ ์ด์ค ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํ์ฌ max์ count ๋์ ๋น๊ต๋ฌธ์ ์ฌ์ฉํ์ฌ ๋ค์ ์ ์ถํ์๋ค. ํ์ง๋ง ์ฌ์ ํ ์๊ฐ ์ด๊ณผ์๋ค.
๊ทธ๋ค์์ list ๋์ dequeu๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด์๋ค. dequeu๋ฅผ ์ฌ์ฉํ์ฌ pop(0) ๋์ popleft๋ฅผ ์ฌ์ฉํ์๋ค. ๊ทธ ๊ฒฐ๊ณผ ํต๊ณผํ ์ ์์๋ค.
์๊ฐ๐ค
์๊ฐ ์ด๊ณผ ๋๋ฌธ์ ํ ๋ฒ์ ํต๊ณผํ๋ ๋ ์ด ์๋ค
๋ฐํ์ ์๋ฌ๋ ์ฃผ์ ์ฐ๋ค๊ฐ ์ฝ๋ ํ ์ค ๋ ๋ ค์ ๋ฐ์...๐ฑ
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 3190_๋ฑ (0) | 2022.03.23 |
---|---|
[Baekjoon] 7569_ํ ๋งํ (0) | 2022.03.22 |
[Baekjoon] 10026_์ ๋ก์์ฝ (0) | 2022.03.20 |
[Baekjoon] 4889_์์ ์ ์ธ ๋ฌธ์์ด (0) | 2022.03.18 |
[Baekjoon] 1850_์ต๋๊ณต์ฝ์ (0) | 2022.03.17 |