문제 링크

다리 만들기

문제 설명

N*N 크기의 이차원 평면 지도에 0은 바다 1은 땅이다. 동서남북으로 육지가 붙어있는 덩어리를 섬이라고 할때, 한 섬과 다른 섬을 잇는 가장 짧은 다리의 길이는?

문제 풀이

시도 1

1. 입력받기
2. bfs를 이용하여 입력받은 지도에서 섬 파악하기 -> 섬별로 번호메김
3. bfs를 이용하여 섬의 바다 근처 땅에서 다른 섬 까지 가는 최단 거리를 찾는다

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
Map = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
islands = {}
answer = N*N+1

for i in range(N):
    Map.append(list(map(int, input().split())))

def in_bound(x,y):
    if x in range(0,N) and y in range(0,N):
        return True
    else:
        return False

def bfs(i,j,count):
    Map[i][j] = count
    queue = deque([(i,j)])
    while queue:
        x,y = queue.popleft()
        Map[x][y] = count

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if in_bound(nx, ny):
                if Map[nx][ny] == 1:
                    queue.append((nx,ny))

#지도에서 각 섬 표시
def find_islands(Map):
    count = 2
    for i in range(len(Map)):
        for j in range(len((Map[0]))):
            if Map[i][j] == 1:
                bfs(i,j,count)
                count += 1

def set_bridge(i,j):
    visited = [[0]*N for _ in range(N)]
    queue = deque([(i,j)])
    while queue:
        x,y = queue.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if in_bound(nx,ny):
                #다른땅에 도착하면
                if Map[nx][ny] != 0 and Map[nx][ny] != Map[i][j]:
                    return visited[x][y]
                #바다고 아직 방문한적 없으면
                if Map[nx][ny] == 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx,ny))
    return N*N+1
#섬 별로 분리하기
find_islands(Map)

for i in range(len(Map)):
    for j in range(len(Map[0])):
        #섬이면
        if Map[i][j] != 0:
            answer = min(answer, set_bridge(i,j))
print(answer)

너무 직관적으로 생각해서 그대로 구현했는지 테스트 케이스는 통과하는데 제출했을때 시간초과가 났다 ,, 굳이 bfs를 한번 더 돌려서 섬을 분리할 필요가 없을 듯 싶었다

시도 2

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
Map = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
islands = {}
answer = N*N+1

for i in range(N):
    Map.append(list(map(int, input().split())))

def in_bound(x,y):
    if x in range(0,N) and y in range(0,N):
        return True
    else:
        return False

def bfs(i,j,count):
    Map[i][j] = count
    queue = deque([(i,j)])
    while queue:
        x,y = queue.popleft()
        Map[x][y] = count

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if in_bound(nx, ny):
                if Map[nx][ny] == 1:
                    queue.append((nx,ny))

#지도에서 각 섬 표시
def find_islands(Map):
    count = 2
    for i in range(len(Map)):
        for j in range(len((Map[0]))):
            if Map[i][j] == 1:
                bfs(i,j,count)
                count += 1

def check_diff_island(x1,y1,x2,y2):
    visited = [[0]*N for _ in range(N)]
    queue = deque([(x1,y1)])
    visited[x1][y1] = 1
    while queue:
        x,y = queue.popleft()
        if x == x2 and y == y2:
            return False
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx,ny):
                if Map[nx][ny] == 1 and visited[nx][ny] != 1:
                    queue.append((nx,ny))
                    visited[nx][ny] = 1
    return True

def set_bridge(i,j):
    visited = [[0]*N for _ in range(N)]
    queue = deque([(i,j)])
    while queue:
        x,y = queue.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if in_bound(nx,ny):
                #다른땅에 도착하면
                if Map[nx][ny] != 0 and check_diff_island(nx,ny, i,j):
                    return visited[x][y]
                #바다고 아직 방문한적 없으면
                if Map[nx][ny] == 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx,ny))
    return N*N+1

for i in range(len(Map)):
    for j in range(len(Map[0])):
        #섬이면
        if Map[i][j] != 0:
            answer = min(answer, set_bridge(i,j))
print(answer)

굳이 섬을 나누지 않고
바다 옆 땅에 대해서 bfs로 다리를 쭉 설치하고 땅에 도착했을때 그 땅이 다른 섬에 속하는지 검사했다.