17472_다리만들기2(Python,설명) 반례...?

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

17472번: 다리 만들기 2

삼성A형 기출문제라서 살짝 긴장하고 풀었다.

 

 

어려운 문제였다... 시간도 많이 걸렸지만 스스로 풀어서 되게 뿌듯한 문제였다.

 

아래와 같은 과정으로 순서대로 해결하여 접근하였다.

 

1. 문제에서 입력으로 준 지도를 2차원 리스트에 저장

2. 각 좌표를 트리구조처럼 만들기 위해 부모 배열을 만든다. 이때 부모배열또한 2차원으로 자신을 가르키도록 만든다.

3. 해당 구조에 맞는 find,union 함수를 만들어주었다.

4. 각 맵을 돌면서 상하좌우의 땅과 비교해서 1인 지점인 두 점이 붙어있으면 union연산을 해서 같은 트리로 만들어준다.

5. 섬들을 저장할 land 배열을 만들고 각 섬마다 대표하는 부모를 하나씩 저장해준다.

6. dist 배열을 하나 만들어 각 섬에서 섬까지의 길이를 저장한다. ( 섬이 최대 6개라 굳이 중복되는 섬을 없애진 않았다.)

7. dist 배열을 길이가 짧은 순으로 정렬해준다.

8. dist 배열을 순회하면서 섬과 섬이 이어져 있지 않다면 union연산으로 연결해주고 길이를 더해주고 다리 개수를 센다

9. 다리 개수와 섬 개수-1 이 같다면 온전히 다 연결된 트리구조이므로 출력하고 그렇지 않으면 -1을 출력한다.

 

 

 

조금 독특하게 2차원 좌표를 자신의 부모로 시작해서 트리를 구성했는데 보다 효율적인 코드가 있을 것 같다는 생각을 하긴 했다. 

 

가장 어려웠던 부분은 -1을 가려내는 작업이었다. 해당 부분때문에 자꾸 오류가 났는데, land 배열에 추가할 때 검사를 하면서 추가하기 때문에 부모가 바뀐 점이 그대로 land에 남아있던 탓이었다.

 

land를 다 만들고 해당 안의 부모가 같은 부분이 있다면 지워주는 작업을 통해서 이를 해결했다.

 

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
dy = [1,0,-1,0]
dx = [0,1,0,-1]
country = []
for _ in range(n):
    country.append(list(map(int,input().split())))

parents = []
for i in range(n):
    tmp = []
    for j in range(m):
        tmp.append([i,j])
    parents.append(tmp)

def find(a):
    i,j = a
    if parents[i][j] == a:
        return a
    parents[i][j] = find(parents[i][j])
    return parents[i][j]
def union(a,b):
    a,b = find(a),find(b)
    if a == b:
        return
    if a[0] > b[0]:
            parents[a[0]][a[1]] = b
    else:
        parents[b[0]][b[1]] = a

land=[]

for i in range(n):
    for j in range(m):
        if country[i][j]:
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if  0<=nx<n and 0<=ny<m and country[nx][ny]:
                    union([i,j],[nx,ny])
            if parents[i][j] not in land:
                land.append(parents[i][j])

for i in range(len(land)):
    land[i] = find(land[i])
new_land = []
for i in land:
    if i not in new_land:
        new_land.append(i)


dist = []
for i in range(n):
    for j in range(m):
        if not country[i][j]:
            continue
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            cnt = 0
            if 0<= nx < n and 0<= ny < m and parents[i][j]==parents[nx][ny]:
                continue
            while(0<= nx < n and 0<= ny < m):
                if country[nx][ny]:
                    break
                cnt += 1
                nx += dx[k]
                ny += dy[k]
            else:
                continue
            if cnt > 1:
                dist.append([cnt,parents[i][j],parents[nx][ny]])
dist.sort()
result = 0
cnt = 1
for i in dist:
    LEN,A,B = i
    if find(parents[A[0]][A[1]]) != find(parents[B[0]][B[1]]):
        result += LEN
        union(A, B)
        cnt +=1
print(result if cnt==len(new_land) else -1)

5 6
1 1 0 0 0 1
1 1 0 0 0 1
0 0 0 0 0 1
0 0 0 0 0 1
1 1 1 1 1 1
2


6 5
1 1 0 0 1
1 1 0 0 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
1 1 1 1 1
2

8 8
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 1 1 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
2


4 8
0 0 0 0 0 0 1 1
1 0 0 1 1 0 1 1
1 1 1 1 0 0 0 0
1 1 0 0 0 1 1 0
-1

9 6
0 0 0 0 1 0
0 0 0 0 0 0 
0 1 0 0 0 1
0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 0 0 1 1
0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 0 0 0 0
12

8 6
0 1 0 0 1 0
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 0 0 1 0
0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 1 1 1 0
정답 : 9

10 10
0 0 0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
1 0 0 1 0 0 0 0 0 1
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 1 1 1 1 0 0 1 1
11

 

내가 문제를 풀며 찾은 반례들은 위와 같다.

 

 

https://www.acmicpc.net/board/view/63536

글 읽기 - 반례모음

위 게시판에서 거의 가져왔는데 복붙하기 편하게 정리해두었다!