BOJ 2146(다리 만들기)풀이

solved.ac 티어 : 골드 3

www.acmicpc.net/problem/2146

2146번: 다리 만들기

태그는 bfs(너비 우선 탐색)이 붙어있긴하지만 bfs를 안쓰고 dfs와 몇번의 전체 탐색만 해주면 된다.

탐색해서 알아내야할 정보는 한 위치로부터 x축으로 가장 가까운 섬과의 거리,그 위치로부터 y축으로 가장 가까운 섬과의 거리, 섬의 번호, 한 위치로부터 가장 가까운 섬의 번호 이렇게 4개를 알아내면 된다.

입력 예시로 예를 들면

                                    # # # 1 2 2 1 # # # 
                                    # # # # 1 2 2 1 # # 
                                    # 1 # # 1 2 2 1 # # 
                                    2 1 # # # 1 2 2 1 # 
                                    3 2 1 # 1 2 3 2 1 # 
                                    9 8 7 6 5 4 3 2 1 # 
                                    0 0 0 0 0 0 0 0 0 0 
                                    4 3 2 1 # # 1 2 3 4 
                                    4 3 2 1 # # # 1 2 3 
                                    0 0 0 0 0 0 0 0 0 0 

이거는 x축으로 가장 가까운 섬과의 거리를 나타낸건데 #은 섬 이고 숫자들은 가장 가까운 섬과의 거리다.

# # # 1 3 7 8 # # # 
# # # # 2 6 7 1 # # 
# 1 # # 1 5 6 2 # # 
1 2 # # # 4 5 3 1 # 
2 3 1 # 1 3 4 4 2 # 
3 4 2 1 2 2 3 5 3 # 
4 5 3 2 1 1 2 6 4 1 
5 6 4 3 # # 1 7 5 2 
6 7 5 4 # # # 8 6 3 
7 8 6 5 1 1 1 9 7 4 

이건 y축으로 가장 가깐운 섬과의 거리를 나타낸것이다.

이 2개를 구해주는 이유는 서로 다른 두 섬을 이으는 직각부분을 찾아야되는데 그럴려면 거리를나타낸 표가 있어야되기 때문이다. 직각부분을 찾는 이유는 한 위치에서 다른 위치로 가는 최소개수는 계단형식으로 가나 ㄴ 모양으로 가나 같기 때문에 직각 부분을 찾는 것이다.

#땅 분류
1 1 1 0 0 0 0 2 2 2 
1 1 1 1 0 0 0 0 2 2 
1 0 1 1 0 0 0 0 2 2 
0 0 1 1 1 0 0 0 0 2 
0 0 0 1 0 0 0 0 0 2 
0 0 0 0 0 0 0 0 0 2 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 3 3 0 0 0 0 
0 0 0 0 3 3 3 0 0 0 
0 0 0 0 0 0 0 0 0 0 

# 한 위치로부터 x축이 가장 가까운 섬의 번호
0 0 0 1 1 2 2 0 0 0 
0 0 0 0 1 1 2 2 0 0 
0 1 0 0 1 1 2 2 0 0 
1 1 0 0 0 1 1 2 2 0 
1 1 1 0 1 1 1 2 2 0 
2 2 2 2 2 2 2 2 2 0 
0 0 0 0 0 0 0 0 0 0 
3 3 3 3 0 0 3 3 3 3 
3 3 3 3 0 0 0 3 3 3 
0 0 0 0 0 0 0 0 0 0 


# 한 위치로부터 y축이 가장 가까운 섬의 번호
0 0 0 1 1 3 3 0 0 0 
0 0 0 0 1 3 3 2 0 0 
0 1 0 0 1 3 3 2 0 0 
1 1 0 0 0 3 3 2 2 0 
1 1 1 0 1 3 3 2 2 0 
1 1 1 1 1 3 3 2 2 0 
1 1 1 1 3 3 3 2 2 2 
1 1 1 1 0 0 3 2 2 2 
1 1 1 1 0 0 0 2 2 2 
1 1 1 1 3 3 3 2 2 2 

이렇게 구해주면

if xland[i][g]!=yland[i][g] and xland[i][g]!=0 and yland[i][g]!=0:
            ma=min(ma,y[i][g]+x[i][g]-1)

이런 방법으로 섬과 섬을 연결하는 다리의 길이를 구해줄수가 있는데 이코드는 한 위치로부터 x축이 가장 가까운 섬의 번호와 한 위치로부터 y축이 가장 가까운 섬의 번호가 같지 않고 둘다 0이 아닐경우

y축으로 가장 가깐운 섬과의 거리+x축으로 가장 가깐운 섬과의 거리-1이 섬과 섬을 연결하는 다리의 길이가 된다.

-1를 해주는 이유는 x길이+y길이 이기 때문에 직각을 이루는 모서리 부분이 곂치기 때문에 1를 빼줘야한다. 이렇게 나온 값들중 가장 작은 값을 출력하면 되는데 여기에 예외를 넣어줘야 한다.

바로 x축을 더하지 않아야될때, 또는 y축을 더하지 않아야될때가 예외인데 이런 예외는 처음에 x와 y따로 거리를 구해서 그 값을 ma에 적용시키고 하면 된다.

import sys;input=sys.stdin.readline;sys.setrecursionlimit(10**9);a=int(input());l=[list(map(int,input().split()))for i in range(a)];x=[[a+1 for i in range(a)]for g in range(a)];xland=[[0 for i in range(a)]for g in range(a)];yland=[[0 for i in range(a)]for g in range(a)];y=[[a+1 for i in range(a)]for g in range(a)];land=[[0 for i in range(a)]for g in range(a)];dx=[0,1,0,-1];dy=[-1,0,1,0];cnt=0;ma=2*a+5
def dfs(y,x,cnt):
    land[y][x]=cnt
    for i in range(4):
        nx=x+dx[i];ny=y+dy[i]
        if nx<0 or nx>=a or ny<0 or ny>=a:continue
        if l[ny][nx]==1 and land[ny][nx]==0:land[ny][nx]=cnt;dfs(ny,nx,cnt)
for i in range(a):
    for g in range(a):
        if land[i][g]==0 and l[i][g]==1:cnt+=1;dfs(i,g,cnt)
for i in range(a):
    ld=0;cnt=0
    for g in range(a):
        if l[i][g]==1:
            if ld!=land[i][g] and ld!=0:ma=min(ma,cnt)
            cnt=0;ld=land[i][g]
        else:cnt+=1
for g in range(a):
    ld=0;cnt=0
    for i in range(a):
        if l[i][g]==1:
            if ld!=land[i][g] and ld!=0:ma=min(ma,cnt)
            cnt=0;ld=land[i][g]
        else:cnt+=1
for i in range(a):
    cnt=0;ch=0;landn=0
    for g in range(a):
        if l[i][g]==1:ch=1;cnt=0;x[i][g]="#";landn=land[i][g]
        else:
            cnt+=ch
            if cnt!=0 and x[i][g]>cnt:xland[i][g]=landn;x[i][g]=cnt
for i in range(a):
    cnt=0;ch=0;landn=0
    for g in range(a-1,-1,-1):
        if l[i][g]==1:ch=1;cnt=0;x[i][g]="#";landn=land[i][g]
        else:
            cnt+=ch
            if cnt!=0 and x[i][g]>cnt:xland[i][g]=landn;x[i][g]=cnt
for g in range(a):
    cnt=0;ch=0;landn=0
    for i in range(a):
        if l[i][g]==1:ch=1;cnt=0;y[i][g]="#";landn=land[i][g]
        else:
            cnt+=ch
            if cnt!=0 and y[i][g]>cnt:yland[i][g]=landn;y[i][g]=cnt
for g in range(a):
    cnt=0;ch=0;landn=0
    for i in range(a-1,-1,-1):
        if l[i][g]==1:ch=1;cnt=0;y[i][g]="#";landn=land[i][g]
        else:
            cnt+=ch
            if cnt!=0 and y[i][g]>cnt:yland[i][g]=landn;y[i][g]=cnt
for i in range(a):
    for g in range(a):
        if xland[i][g]!=yland[i][g] and xland[i][g]!=0 and yland[i][g]!=0:ma=min(ma,y[i][g]+x[i][g]-1)
print(ma)