처음 작성했던 코드.함수를 두개 만들어 하나는 섬을 구분하기 위한 bfs 함수, 하나는 거리정보를 구하기 위한 build_bridge 함수로 동작할 수 있도록 작성했다.
함수를 두 개 활용해야 한다는 점은 잘 생각했으나, 메인 함수에서 모든 좌표를 방문하면서 build_bridge 함수를 수행한다는 것에서 시간이 너무 소요되었는지 시간초과가 발생했다.
from collections import deque
def build_bridge(sx,sy):
global ans
q = deque()
q.append((sx,sy))
while q:
x,y = q.popleft()
if v[y][x] != 0 and v[y][x] != v[sy][sx]:
ans = min(ans, visited[y][x]-1)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
else:
if (v[ny][nx] == 0 or v[ny][nx] != v[sy][sx]) and visited[ny][nx] == 0:
visited[ny][nx] = visited[y][x] + 1
q.append((nx,ny))
def bfs(sx,sy):
global islandNum
queue = deque()
queue.append((sx,sy))
v[sy][sx] = islandNum
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
else:
if board[ny][nx] != 0 and v[ny][nx] == 0:
v[ny][nx] = islandNum
queue.append((nx,ny))
n = int(input())
board = [list(map(int,input().split())) for _ in range(n)]
v = [[0] * n for _ in range(n)]
dx = [0,1,0,-1]
dy = [-1,0,1,0]
islandNum = 1
for i in range(n):
for j in range(n):
if board[i][j] == 1 and v[i][j] == 0:
bfs(j,i)
islandNum += 1
ans = n*2
for i in range(n):
for j in range(n):
visited = [[0] * n for _ in range(n)]
if v[i][j] != 0 and visited[i][j] == 0:
build_bridge(j,i)
print(ans)
다른 코드 및 설명
섬 번호만큼 for문을 돌면서 build_bridge 함수 내에서 섬 번호에 해당하는 좌표를 큐에 넣어주고 큐가 빌때까지 다음 좌표 탐색을 실시한다.
from collections import deque
#섬 구분하기
def bfs(sx,sy):
global islandNum #섬 번호 변수
queue = deque()
queue.append((sx,sy))
v[sy][sx] = islandNum #리스트 v에 섬 번호를 저장한다. 현재 좌표의 섬 번호는 islandNum.
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
else:
#다음 좌표가 육지(1)이고, 아직 방문안했다면
if board[ny][nx] != 0 and v[ny][nx] == 0:
#다음 좌표에 섬 번호 표시한다.
v[ny][nx] = islandNum
queue.append((nx,ny))
#다리 놓기
def build_bridge(num):
global ans
#거리를 저장할 리스트를 생성한다. 초기 좌표값은 -1
distance = [[-1]*n for _ in range(n)]
q = deque()
#섬 번호를 표시한 그리드를 돌면서 섬 번호에 해당하는 좌표를 큐에 넣는다.
for i in range(n):
for j in range(n):
if v[i][j] == num:
q.append((j,i))
#거리는 0부터 시작하므로 섬에 해당하는 좌표 값0으로 갱신한다.
distance[i][j] = 0
while q:
x,y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
#범위를 벗어나면 다음으로
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
#다음 좌표의 섬 번호가 0 초과(육지)이고, 현재 섬 번호가 아니라면
if v[ny][nx] > 0 and v[ny][nx] != num:
#현재 좌표의 거리 정보와 ans 중 최소값을 ans에 넣는다.
ans = min(ans, distance[y][x])
return #리턴해준다.
#만약 바다이고, 아직 방문 안했다면, 거리 값을 갱신한다.
if v[ny][nx] == 0 and distance[ny][nx] == -1:
distance[ny][nx] = distance[y][x] + 1
q.append((nx, ny))
n = int(input())
board = [list(map(int,input().split())) for _ in range(n)]
v = [[0] * n for _ in range(n)]
dx = [0,1,0,-1]
dy = [-1,0,1,0]
#가로세로 i,j에 해당하는 좌표에 섬 번호를 바꾼다.
islandNum = 1
for i in range(n):
for j in range(n):
if board[i][j] == 1 and v[i][j] == 0:
bfs(j,i)
islandNum += 1 #bfs한번 실행되고 나면 섬 번호를 1씩 올려준다.
ans = n*2
for i in range(1, islandNum):
build_bridge(i)
print(ans)
