링크
백준 2146 다리만들기
이 문제의 경우 bfs+bfs로 풀거나 dfs+bfs로 푸는 문제이다.
뭐랄까.. 삼성 a형 문제를 푸는 느낌이었다. 굉장히 코드가 길고 기존에 아는걸 아주 살짝 응용해야하는..?
마지막에 다리의 길이를 세어주는거에서 문제가 생겨 해당부분만 다른사람의 코드를 참고했다. 조금만 더 생각하면 알만한거였는데 보고나니 조금 아쉽다.
먼저 bfs1은 각각의 땅을 구분해주는 함수이다.
land라는 인자값을 넘겨주고 함수를 호출할 때 land를 -1씩 빼주어 음수로 땅들을 구분했다.
땅들을 구분하며 바다와 붙어있는 곳의 좌표는 따로 저장해주었다.
음수로 구분한 이유는 처음엔 해당 배열에 그대로 거리값을 양수로 주면서 다리길이를 구하려고 했던건데 결과적으로 해당 방법으로 다리길이를 구하지 않아 괜한일이됐다.
bfs2는 간척사업을 하는 함수이다.
처음엔 땅끝의 좌표를 하나하나 받아서 bfs로 최소값을 구하려 했는데 너무 비효율적이었다.
그래서 모든 땅끝을 한번에 돌며 땅을 점차 넓혀주면서 땅이 최소로 연결되는 지점을 찾았다.
여기서 문제가 생겼는데, 다리길이가 원인모를 이유로 차이가 나다 안나다 하는 것이었다.
이부분에서 다른사람의 코드를 참고했다.
두 가지 경우가 있을 수 있다. 이동하려는 좌표의 그룹번호가 현재 그룹번호보다 낮은 경우 또는 높은 경우이다.
낮은 경우라면 아래와 같은 경우이다.-1 0 0 -2 -> -1 -1 0 -2 -> -1 -1 -2 -2 -> -1 -1 -2 -2 -1이 경우라면 모든 땅이 한 번씩 간척사업을 한 후에 이미 다리가 연결된 것이다.
하지만 이 경우를 두 번째 간척사업을 진행하던 도중 알게 된 것이다.
즉, 현재 간척사업 횟수는 2이지만 1일 때 이미 결정된 것이기 때문에 i번째 간척사업 중이라면 (i-1)*2 의 길이의 다리가 형성되게 된다.
반대로 높은 경우라면 아래와 같은 경우이다.
-1 0 0 0 -2 -> -1 -1 0 0 -2 -> -1 -1 0 -2 -2 -> -1 -1 -1 -2 -2 -> -1 -1 -1 -2 -2 -2이 경우는 각자 두 번씩 간척사업을 하려는 도중에 다리가 연결된 경우이다.
그러나 중복된 곳에 간척을 하려고 했기 때문에 1개의 블록이 중복된다.
즉, i번째 간척사업 중에 중복된 곳에 다리를 놓게 되기 때문에 i*2-1 의 길이의 다리가 형성된다.
이부분을 몰라 한시간을 넘게 해당부분만 생각하고 고치고 있었는데 참고한 코드로 짜보니 통과할 수 있었다.
앞으로 점점 어려운 문제를 풀텐데 이런부분을 잘 생각해야 할 것 같다.
정답 코드
from collections import deque
def bfs1(r, c, land):
q = deque()
q.append((r, c))
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < N and 0 <= nc < N:
if visited[nr][nc] == 0 and arr[nr][nc] == 1: #방문안했고 땅이면
visited[nr][nc] = land
q.append((nr, nc))
elif visited[nr][nc] == 0 and arr[nr][nc] == 0: #방문안했고 땅 옆에 붙어있는 바다면
end.append((r, c)) #땅의 끝
def bfs2(end):
cnt = 0 #반복횟수
ans = 987654321
while end:
cnt += 1
for _ in range(len(end)):
r, c = end.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < N and 0 <= nc < N:
if visited[nr][nc] == 0 or visited[nr][nc] == 1: #바다거나 땅옆에 있는 바다
visited[nr][nc] = visited[r][c] #땅 확장
end.append((nr, nc))
elif visited[nr][nc] != visited[r][c]: #우리땅 아님
if visited[nr][nc] < visited[r][c]:
ans = min(((cnt - 1) * 2), ans)
if visited[nr][nc] > visited[r][c]:
ans = min(((cnt * 2) - 1), ans)
return ans
N = int(input())
arr = [] #지도
end = deque() #육지의 끝에 붙어있는 바다 (다리의 시작점)
land = -1 #육지 분리해서 표시하기 위함
visited = [([0] * N) for _ in range(N)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
for _ in range(N):
arr.append(list(map(int, input().split())))
for i in range(N):
for j in range(N):
if arr[i][j] == 1 and visited[i][j] == 0:
visited[i][j] = land
bfs1(i, j, land)
land -= 1
print(bfs2(end))알게된 것👨💻
- bfs의 중복사용, 경우를 잘 생각해보자.
