728x90
반응형
※ 문제링크
해당문제는 BFS를 활용하여 해결할 수 있는 문제였다. 처음 생각한 방법은 완전 탐색을 통해 섬의 좌표값을 모두 확인한 후 BFS함수를 한번씩 돌려가며 다른 섬에서 출발한 다리와 만날때 cnt값을 반환하는 것이었는데, 해당 방식으로 구현하면 다리의 길이가 될 수 있는 경우의 수가 2개가 되어 정확한 값을 구하지 못하는 문제가 있어 각 섬에 고유번호를 부여하고, 맵의 각 좌표의 방문기록을 일일히 기록하며, 섬의 번호가 다른 지점이 발생할 때, 각 섬에서 출발한 다리길이의 숫자를 구해서 리턴하는 방식으로 구현하였다. 자세한 풀이방법과 코드는 아래와 같다.
1. 입력받은 값을 2차원 배열로 변환하여 그래프 형태로 만들어준다.
2. 각각의 섬에 고유번호를 부여할 BFS함수와 지도의 각 지점의 방문기록을 확인할 2차원 배열을 만들어 준 후 섬에 번호를 부여한다.
3. 각 섬에서 출발한 다리의 길이를 기록할 2차원 배열을 만들고, 섬과 다리설치여부를 확인할 BFS함수를 작성해준다.
4. 반복문을 통해 다리가 만나는 지점이 발생할 때 해당 다리의 총 길이를 구하고, 다리의 총 길이를 기록한 리스트에서 최소값을 반환하여 출력해준다.
+ 시간 및 메모리 단축을 위해 sys를 사용하였으며, 개행문자에 유의하였다.
from collections import deque
import sys
# input = sys.stdin.readline
N = int(input())
field = []
for _ in range(N):
field.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False for _ in range(N)] for _ in range(N)]
length = [[0 for _ in range(N)] for _ in range(N)]
queue = deque()
def check_island(x, y, island_num):
island = deque()
visited[y][x] = True
island.append([x, y])
field[y][x] = island_num
queue.append([x, y, island_num])
while island:
x, y = island.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if field[ny][nx] == 1 and visited[ny][nx] == False:
field[ny][nx] = island_num
visited[ny][nx] = True
island.append([nx, ny])
queue.append([nx, ny, island_num])
def bridge():
ans_list = []
for _ in range(len(queue)):
x, y, island_num = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if field[ny][nx] == 0 and visited[ny][nx] == False:
visited[ny][nx] = True
field[ny][nx] = island_num
length[ny][nx] = cnt
queue.append([nx, ny, island_num])
if field[ny][nx] != 0 and island_num != field[ny][nx]:
ans_list.append(length[ny][nx] + length[y][x])
if len(ans_list) != 0:
return min(ans_list)
return 0
island_num = 1
queue = deque()
for i in range(N):
for k in range(N):
if field[k][i] == 1 and visited[k][i] == False:
check_island(i, k, island_num)
island_num += 1
ans = 0
cnt = 0
while ans == 0:
cnt += 1
ans = bridge()
print(ans)
P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 17142번 연구소3 / 사용언어 : 파이썬(python) (0) | 2022.01.22 |
---|---|
[BOJ] 11404번 플로이드 / 사용언어 : 파이썬(python) (0) | 2022.01.21 |
[BOJ] 9370번 미확인 도착지 / 사용언어 : 파이썬(python) (0) | 2022.01.17 |
[BOJ] 1504번 특정한 최단 경로 / 사용언어 : 파이썬(python) (0) | 2022.01.16 |
[BOJ] 10026번 적록색약 / 사용언어 : 파이썬(python) (0) | 2022.01.15 |
댓글