1. 문제 링크 및 문제
문제링크 : https://www.acmicpc.net/problem/2146
1-1 문제 요약
:N*N크기의 맵에 바다와 여러개의 육지정보가 담겨져있음. 바다=0, 육지=1
육지와 육지 사이의 최단거리를 구하는 문제 (각 육지: 상하좌우로 연결된 1)
2. 해결 방법 생각해보자 ...
1. 각 육지를 구분할 방법이 필요해!
1-1. 방법 : 반복문을 돌려서 각 육지의 번호를 다르게 표시
2. 구분된 육지들 사이의 최단거리를 구해야 하므로 BFS 를 사용!
2-1 시작지점,종료지점,조건 생각
3. 코드
해결방법순 코드
1. 육지를 구분할 방법이 필요해!
먼저 전체맵에서 반복문을 돌리다 육지가 나온다면 ( == 1이 나온다면 )
for i in range(N):
for j in range(N):
if array[i][j] == 1 and not visited[i][j]:
DevideLandBFS(i,j,LandCount)
LandCount += 1
BFS를 돌려 상하좌우로 이동하며 해당 육지를 전부 LandCount란 수로 바꿔주고, 다음 육지엔 LandCount + 1 을 보낸다.
def DevideLandBFS(x,y,LandCount):
q = deque()
q.append((x,y))
array[x][y] = LandCount
visited[x][y] = True
while q :
x,y = q.popleft()
for i in range(4):
xx, yy = x+dx[i],y+dy[i]
if xx<0 or xx>=N or yy<0 or yy>=N: continue
if array[xx][yy] == 1 and not visited[xx][yy]:
q.append((xx,yy))
visited[xx][yy] = True
array[xx][yy] = LandCount예시로 이해 ) 백준예시1 을 넣고 DevideLandBFS 를 돌리면 이러한 결과가 나옴
2. 구분된 육지들 사이의 최단거리를 구해야 하므로 BFS 를 사용!
@ 최단거리 계산 = 거리 계산할 배열 생성 ( dist )
- 1부터 LandCount 개의 육지가 있으므로, 1,LandCount 까지 반복문을 돌림.
1섬에서 다른섬까지, 2섬에서 다른섬까지, 3섬에서 다른섬까지의 경우의 수
for nowLand in range(1,LandCount):
FindMinDist(nowLand)- FindMinDist(nowLand) 함수 설명
2-1. (0,0)부터 (N,N) 중 array[x][y]가 nowLand인 경우에 q 에 추가 , 출발지이므로 dist[x][y] = 0
2-2. q 에서 하나씩 꺼내 상하좌우로 이동하며 바다일 때, 다른 섬일 때 코드실행
바다일 때 : dist[xx][yy] == -1 이며, array[xx][yy] == 0 인 경우
다른섬일 때 : array[xx][yy] >0 이며, array[xx][yy] != nowLand 인 경우
MinDistance = N*N
count = 0
def FindMinDist(nowLand):
global count,MinDistance
q = deque()
dist = [[-1]*N for _ in range(N)]
#2-1
for i in range(N):
for j in range(N):
if array[i][j] == nowLand :
q.append((i,j))
dist[i][j] = 0
#2-2
while q:
x,y = q.popleft()
for i in range(4):
xx, yy = x+dx[i], y+dy[i]
if xx<0 or xx>=N or yy<0 or yy>=N : continue
if array[xx][yy] >0 and array[xx][yy] != nowLand :
MinDistance = min(MinDistance, dist[x][y])
return
if dist[xx][yy] == -1 and array[xx][yy] == 0 :
dist[xx][yy] = dist[x][y]+1
q.append((xx,yy))예시로 이해) FindMinDist(1) 1섬에서 다른섬까지의 거리를 계산할 때의 distance배열
현재섬 : 0, 바다: 계산된 거리, 다른섬: -1
[0, 0, 0, 1, 2, 3, 4, -1, -1, -1]
[0, 0, 0, 0, 1, 2, 3, 4, -1, -1]
[0, 1, 0, 0, 1, 2, 3, 4, -1, -1]
[1, 1, 0, 0, 0, 1, 2, 3, 4, -1]
[2, 2, 1, 0, 1, 2, 3, 4, -1, -1]
[3, 3, 2, 1, 2, 3, 4, -1, -1, -1]
[4, 4, 3, 2, 3, 4, -1, -1, -1, -1]
[-1, -1, 4, 3, -1, -1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]- 전체코드
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
array = [list(map(int, input().split())) for _ in range(N)]
visited = [[False]*N for _ in range(N)]
dx,dy = [-1,0,1,0],[0,1,0,-1]
LandCount = 1
def DevideLandBFS(x,y,LandCount):
q = deque()
q.append((x,y))
array[x][y] = LandCount
visited[x][y] = True
while q :
x,y = q.popleft()
for i in range(4):
xx, yy = x+dx[i],y+dy[i]
if xx<0 or xx>=N or yy<0 or yy>=N: continue
if array[xx][yy] == 1 and not visited[xx][yy]:
q.append((xx,yy))
visited[xx][yy] = True
array[xx][yy] = LandCount
for i in range(N):
for j in range(N):
if array[i][j] == 1 and not visited[i][j]:
DevideLandBFS(i,j,LandCount)
LandCount += 1
MinDistance = N*N
count = 0
def FindMinDist(nowLand):
global count,MinDistance
q = deque()
dist = [[-1]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if array[i][j] == nowLand :
q.append((i,j))
dist[i][j] = 0
while q:
x,y = q.popleft()
for i in range(4):
xx, yy = x+dx[i], y+dy[i]
if xx<0 or xx>=N or yy<0 or yy>=N : continue
if array[xx][yy] >0 and array[xx][yy] != nowLand :
MinDistance = min(MinDistance, dist[x][y])
return
if dist[xx][yy] == -1 and array[xx][yy] == 0 :
dist[xx][yy] = dist[x][y]+1
q.append((xx,yy))
for nowLand in range(1,LandCount):
FindMinDist(nowLand)
print(MinDistance)! 아차차
BFS 문제라는 걸 알고 풀었음에도 접근하기 굉장히 어려웠고, 두번째 풀어보는 건데도 다른 분들의 코드 없이는 해결하지 못했다. 저번엔 손도 못댔으나 이번엔 손이라도 댄 게 어딘가! 다음에 풀 땐 안보고 풀 수 있을 것 같다 ㅎㅎ(제발)
다음에 풀 땐 꼭 생각하고 반영하자 !
1. 최단거리 계산인데 distance 배열 생성도 안하고 count 로 하고 있었음.
2. 현재섬을 0, 바다 및 다른 섬 -1 로 거리를 계산하는 코드를 보고 저번에도 감탄했는데 또 감탄함.
3. array[i][j] == nowLand 일 때 바로 q를 실행하고 빼주는 것이 아닌, 현재 섬의 모든 좌표를 q에 넣어두고 , 실행한다는 것 !
