문제

https://www.acmicpc.net/problem/2146

나의 코드

"""
1. 아이디어
이거.. 간단하게 말하자면 일단 섬이 나뉘어져 있으니깐 첫 번째 섬은 2로 
두 번째 섬은 3으로 이런식으로 숫자로 구별을 한다(bfs를 돌려서)

그다음이 중요한데 섬들 간의 최단거리를 세기 위해서 dis[][]라는 2차원 배열을 만들어서 
여기에는 거리만 셀 수 있도록 한다. 그리고 다른 섬을 만났을 때 거리값을 return하는
방식으로 작성하면 된다.

2. 시간복잡도
O(N^2) 코드가 길긴 하지만 공간복잡도만 늘어날 뿐 시간복잡도는 다른 bfs문제랑 다를 거 없다.
"""

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
map = [ list(map(int, input().split())) for _ in range(n) ]
island = 1

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]

def bfs(x, y): # 섬들을 숫자를 이용해서 서로 구분해준다.
    global island
    island += 1
    q = deque([(x, y)])
    map[x][y] = island

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]
            if 0 <= mx < n and 0 <= my < n:
                if map[mx][my] == 1:
                    map[mx][my] = island
                    q.append((mx, my))

for i in range(n):
    for j in range(n):
        if map[i][j] == 1:
            bfs(i, j)

answer = []

def bfs2(x, y): # 거리만 세는 2차원 배열을 만들어서 다른 섬을 만나는 경우 return하도록 한다.
    now_island = map[x][y]
    dis = [ [0] * n for _ in range(n) ] # 거리만 세는 2차원 배열
    q = deque([(x, y)])

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]
            if 0 <= mx < n and 0 <= my < n:
            	# 처음 가는 거리인 경우
                if map[mx][my] == 0 and dis[mx][my] == 0:
                    dis[mx][my] = dis[px][py] + 1
                    q.append((mx, my))
                   
                # 0이 아닌 숫자를 만났는데 그게 현재 섬의 숫자가 아닌경우
                elif map[mx][my] != 0 and map[mx][my] != now_island: 
                    answer.append(dis[px][py])
                    return

for i in range(n):
    for j in range(n):
        if map[i][j] > 0:
            bfs2(i, j)

print(min(answer))
    

처음 코드

from sys import stdin
from collections import deque
input = stdin.readline

n = int(input())
map = [ list(map(int, input().split())) for _ in range(n) ]
island = 2
ans = n*n

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]

def bfs(x, y):
    global island
    map[x][y] = island
    q = deque([(x, y)])

    while q:
        px, py = q.popleft()
        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]
            if 0 <= mx < n and 0 <= my < n:
                if map[mx][my] == 1:
                    map[mx][my] = island
                    q.append((mx, my))

for i in range(n):
    for j in range(n):
        if map[i][j] == 1:
            bfs(i, j)
            island += 1

def bfs2(island):
    global ans
    dis = [ [-1] * n for _ in range(n) ]
    q = deque()

    for i in range(n):
        for j in range(n):
            if map[i][j] == island:
                q.append((i, j))
                dis[i][j] = 0

    while q:
        px, py = q.popleft()
        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]
            if 0 <= mx < n and 0 <= my < n:
                if map[mx][my] == 0 and dis[mx][my] == -1:
                    dis[mx][my] = dis[px][py] + 1
                    q.append((mx, my))
                elif map[mx][my] > 0 and map[mx][my] != island:
                    ans = min(ans, dis[px][py])
                    return

for i in range(2, island):
    bfs2(i)

print(ans)

느낀점

이거 맨 처음에 풀때는 3.4초가 걸렸는데 두 번째 풀때 0.5초가 걸렸다. 시간 복잡도가 확 줄어들었는데 그 이유를 생각해보니 bfs내에 코드에서 차이가 있는데 첫 번째 풀때는 반복문 안에 min함수를 그냥 넣었는데 두번째 풀때는 answer이라는 리스트를 만들어서 append로 모든 값을 집어넣고(O(n)) 마지막에 출력할때 min함수를 썼다. (반복문 내에서 안쓰고)

앞으로 반복문 내에서 다른 함수를 또 쓸때는 시간복잡도 초과하는지 확인을 한 번 해보자.