[파이썬] 백준 17472 - 다리 만들기 2

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

[17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net](https://www.acmicpc.net/problem/17472)

---

풀이

1. 섬을 구분하기

2. 섬과 섬 사이의 거리에 따른 다리건설 가능 여부 + 연결 가능여부를 확인

3. 탐색을 통해 가장 짧은 거리를 찾기

 

1. 섬 구분하기

섬의 입력은 0과 1로 이루어진 NxM형태이다.

여기에 STR 0으로 둘러싸줌

 

각 섬을 딕셔너리 형태로 넘버링한 것을 key로 넣고 섬의 index (y,x)들을 list형태로 value에 담아줘서 섬을 구분하고

아스키코드를 이용하여 각 섬의 1을 해당 섬의 넘버링 + 64를 통해 아스키코드로 바꿔준다.

 

왜 이렇게 하냐면 copy를 최대한 안쓰기 위해서이다. 이렇게 하면 copy를 쓰지 않고 리스트를 탐색하며 int형 0을 탐색해가며 다리를 놓을 수 있다.

 

 

2. 섬과 섬 사이의 거리에 따른 다리건설 가능 여부 + 연결 가능여부 확인하기

 

island 딕셔너리를 섬의 번호로 접근하며 다른 섬과의 거리와 연결 여부를 확인한다.

델타탐색 + while문을 통해 해당 방향을 쭉 탐색하며 거리와 연결 여부를 동시에 확인하고 거리가 2 이상이면 connect 딕셔너리에 {섬번호:[연결가능한섬1,다리길이1,연결가능한섬2,다리길이2]} 형태로 저장

 

3. 탐색을 통해 가장 짧은 거리를 찾기

bfs 재귀를 통해 탐색했다.

 

코드

import sys
def input():
    return sys.stdin.readline().rstrip()

# 입력받기
N, M = map(int,input().split())
one = [['0'] * (M+2)]
for i in range(N):
    tmp = ['0'] + list(map(int,input().split())) + ['0']
    one.append(tmp)
one.append(list(['0'] * (M+2)))

# 섬 구분하기
def findIsland(y, x, idx):
    global one
    d = [(-1,0),(1,0),(0,-1),(0,1)]
    for dy,dx in d:
        ny = y + dy
        nx = x + dx
        if one[ny][nx] == 1:
            one[ny][nx] = chr(64+idx)
            island[idx].append((ny,nx))
            findIsland(ny,nx,idx)

island = {}
island_lst = []
idx = 1
for y in range(N+2):
    for x in range(M+2):
        if one[y][x] == 1:
            one[y][x] = chr(idx+64)
            island[idx] = [(y,x)]
            findIsland(y,x,idx)
            island_lst.append(idx)
            idx += 1

# 연결 가능한 섬과의 거리 찾기
connect = {key:[] for key in island_lst}

def findAnotherIsland(idx):
    global connect
    d = [(-1,0),(1,0),(0,-1),(0,1)]
    for y,x in island[idx]:
        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            cnt = 0
            while one[ny][nx] == 0:
                cnt += 1
                ny += dy
                nx += dx
            else:
                if str(one[ny][nx]).isalpha():
                    a = ord(one[ny][nx]) - 64
                    if cnt > 1 and a in island_lst:
                        if [a,cnt] not in connect[idx]:
                            connect[idx].append([a,cnt])


for i in island_lst:
    findAnotherIsland(i)

# 탐색

answer = 600

def bfs(n,visited,cnt,stk):
    global answer
    if cnt >= answer:
        return

    if 0 not in visited:
        answer = min(answer, cnt)
        return
    for i in connect[n]:
        if not visited[i[0]]:
            visited[i[0]] = 1
            bfs(i[0], visited, cnt+i[1],stk + [n])
            visited[i[0]] = 0
    else:
        if stk:
            a = stk.pop()
            bfs(a,visited, cnt, stk)

visited = [1,1] + [0] * (len(island_lst)-1)

bfs(1,visited,0,[])

# answer이 초깃값이면 모든 섬의 연결 자체가 안되는거임

if answer != 600:
    print(answer)
else:
    print(-1)