백준 2573문제
이문제의 해결과정은 이렇다
1. matrix 전체를 순회하며 빙산이 있는곳을 찾는다
2. 빙산이 있는곳을 찾았을때 처음 지점부터 DFS를 수행해주면서
주변 바다의 개수만큼 matrix값을 빼준다
3. DFS가 2번이상 수행된다면 그 때가 빙산이 분리되는 시점 다음 반복문이 실행 될 때 이므로
그 때 루프제어 변수 -1 값을 result값으로 출력해준다.
입력
1. 첫째 줄에는 행과 열의 개수를 나타내는 N과 M을 공백 사이에 두고 입력 ( 3 <= N, M <= 300)
2. 둘째 줄부터는 matrix정보 입력
출력
몇년후에 빙산이 두개이상으로 나눠 지는지 년수 정수로 출력
파이썬 코드
# 입력
# 1. 첫째 줄에는 행과 열의 개수를 나타내는 N과 M을 공백 사이에 두고 입력 ( 3 <= N, M <= 300)
# 2. 둘째 줄부터는 matrix정보 입력
# 출력
# 몇년후에 빙산이 두개이상으로 나눠 지는지 년수 정수로 출력
import sys
import copy
sys.setrecursionlimit(10**6)
#DFS탐색으로 1년동안의 빙산을 녹여주는 함수
def DFS(y, x, N, M, matrix, visit):
visit[y][x] = 1
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
#(y, x)위치에 따라 빙산 녹이기
count = 0
for i in range(4):
newY = dy[i] + y
newX = dx[i] + x
if newY >= 0 and newY < N and newX >= 0 and newX < M:
if(matrix[newY][newX] == 0):
count += 1
matrix[y][x] -= count
if matrix[y][x] < 0:
matrix[y][x] = 0
#상하좌우 순으로 DFS탐색
for i in range(4):
newY = dy[i] + y
newX = dx[i] + x
if newY >= 0 and newY < N and newX >= 0 and newX < M:
if matrix[newY][newX] != 0 and visit[newY][newX] == 0:
visit[newY][newX] = 1
DFS(newY, newX, N, M, matrix, visit)
return
#행과 열의 크기 입력
N, M = map(int, sys.stdin.readline().split())
#matrix 입력
matrix = [[0] * M for _ in range(N)]
for i in range(N):
matrix[i] = list(map(int, sys.stdin.readline().split()))
count = 0
result = 0
#k년 동안의 빙산 녹이기
for k in range(10):
visit = [[0] * M for _ in range(N)]
#1년 동안 빙산 녹이기
for i in range(N):
for j in range(M):
if matrix[i][j] != 0 and visit[i][j] == 0:
DFS(i, j, N, M, matrix, visit)
count += 1
print('-------', k+1, '년후 빙산','-------')
for i in range(N):
for j in range(M):
print(matrix[i][j], end = ' ')
print()
if count > 1:
result = k
break;
else:
count = 0
print(result)
위 코드로 제출햇더니 틀렷다 그 이유는 DFS탐색을 하면서 matrix값을 수정했으며
이렇게 되면 방금녹이 빙산에 인접한 빙산의 인접한 바다의 개수가 달라지며
따라서 다른 tmp_matrix를 만들어서 안전하게 수정하기로 해봤다
그리고 이것까지 포함하여 DFS를 수행하려다 보니 매개변수로 tmp_matrix를 넘겨줘야 하여
melt함수와 dfs탐색을 몇번했는지에 대해 count하는 함수로 구분하여 이문제를 해결해 보려 해봤다.
하지만 이 방식으로도 해결되지가 않았다 !!!!
그리고 계속 1시간 가까이 코드를 읽어봤지만 풀리지않았고 이에따른 스트레스 때문에 코딩공부를 며칠쉬다가 다시 도전했다 하지만 이때 나는 컴퓨터앞에 앉아있지 않았고 노트를 잡고 생각하다가 모르겠으면 일상을 살다가 계속 잔심만 남겼다가 방법이 떠올랐다 나는 k반복문을 돌릴때 당연히 빙산의 높이 최댓값 년도안에는 모든 빙산이 녹을 것이란 바보같은 생각을 했고 따라서 나는 K반복문 대신에 무한 루프를 돌리고 melt작업이 진행알되었을 때 count는 0이니까 모든 빙산이 녹았을 때 경우이고 이때 무한 루프를 종료하는 식으로 진행해봤고 이 코드는 이러하다
파이썬 코드
# 입력
# 1. 첫째 줄에는 행과 열의 개수를 나타내는 N과 M을 공백 사이에 두고 입력 ( 3 <= N, M <= 300)
# 2. 둘째 줄부터는 matrix정보 입력
# 출력
# 몇년후에 빙산이 두개이상으로 나눠 지는지 년수 정수로 출력
import sys
import copy
from collections import deque
#BFS탐색으로 1년동안의 빙산을 녹여주는 함수
def melt(y, x, matrix, N, M, visit):
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
tmp_matrix = copy.deepcopy(matrix)
Q = deque()
Q.append([y, x])
visit[y][x] = 1
while Q:
curY, curX = Q.popleft()
#현재위치 빙산 녹여주기
count = 0
for i in range(4):
nearY = curY + dy[i]
nearX = curX + dx[i]
if nearY >= 0 and nearY < N and nearX >= 0 and nearX < M:
if matrix[nearY][nearX] == 0:
count += 1
tmp_matrix[curY][curX] = matrix[curY][curX] - count
if tmp_matrix[curY][curX] < 0:
tmp_matrix[curY][curX] = 0
#다음 녹여줄 빙산의 좌표 큐에 apppend
for i in range(4):
newY = curY + dy[i]
newX = curX + dx[i]
if newY >= 0 and newY < N and newX >= 0 and newX < M:
if matrix[newY][newX] != 0 and visit[newY][newX] == 0:
visit[newY][newX] = 1
Q.append([newY,newX])
return tmp_matrix, visit
#행과 열의 크기 입력
N, M = map(int, sys.stdin.readline().split())
#matrix 입력
matrix = [[0] * M for _ in range(N)]
for i in range(N):
matrix[i] = list(map(int, sys.stdin.readline().split()))
count = 0
result = 0
k = 0
#k년 동안의 빙산 녹이기
while True:
visit = [[0] * M for _ in range(N)]
#1년 동안 빙산 녹이기
for i in range(N):
for j in range(M):
if matrix[i][j] != 0 and visit[i][j] == 0:
matrix, visit = melt(i, j, matrix, N, M, visit)
count += 1
# print('-------', k+1, '년후 빙산','-------')
# for i in range(N):
# for j in range(M):
# print(matrix[i][j], end = ' ')
# print()
if count == 0:
break;
elif count > 1:
result = k
break;
else:
count = 0
k += 1
print(result)
정말 이문제 때문에 스트레스 받았지만 항상 그래왔듯이 난 이겨냈고 다음에도 이런 어려움따위 이겨낼 것이다!!!!
