728x90
난이도 : 골드4
풀이일 : 04156
https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐
1차 시도 오답 -> 34% 시간 초과
import sys
def melt(arr):
global day
temp = [[0] * m for _ in range(n)]
flag = False # 빙산 존재 여부
# 녹을 높이 구하기
for i in range(n):
for j in range(m):
if arr[i][j]:
flag = True
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0 <= ni < n and 0 <= nj < m and arr[ni][nj] == 0:
temp[i][j] += 1
if flag:
# 실제 녹이기
day += 1
for i in range(n):
for j in range(m):
if arr[i][j] >= temp[i][j]:
arr[i][j] -= temp[i][j]
else:
arr[i][j] = 0
ice(arr)
return
else:
return print(day)
# 빙산 개수 세기
def ice(arr):
visited = [[0] * m for _ in range(n)]
queue = []
count = 0
p = 0
for a in range(n):
for b in range(m):
if arr[a][b] and visited[a][b] == 0:
count += 1
queue.append(a)
queue.append(b)
visited[a][b] = 1
while p < len(queue):
i = queue[p]
j = queue[p+1]
p += 2
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0 <= ni < n and 0 <= nj < m and visited[ni][nj] == 0 and arr[ni][nj]:
queue.append(ni)
queue.append(nj)
visited[ni][nj] = 1
if count > 1:
return print(day)
return melt(arr)
n, m = list(map(int, sys.stdin.readline().split()))
sea = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
day = 0
melt(sea)코드 구성
1. 빙산 높이를 줄일 melt 함수로 인접 바다 수를 temp 저장 후 높이 차감
-> 방금 바다가 된 지점을 세지 않기 위해 temp 사용
2. 시간 효율을 위해 BFS 구현 시 pop 대신 포인터 p를 활용, 인덱스로 접근
3. 녹인 후 빙산의 개수 세기
-> BFS로 빙산의 개수를 세고, 두 개 이상이 되었다면 시간 반환
틀린 이유
1. 시간 초과 -> 제출 언어 pypy로 변경
2차 시도 오답 -> 59% 틀렸습니다
import sys
def melt(arr):
global day
temp = [[0] * m for _ in range(n)]
flag = False # 빙산 존재 여부
# 녹을 높이 구하기
for i in range(n):
for j in range(m):
if arr[i][j]:
flag = True
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0 <= ni < n and 0 <= nj < m and arr[ni][nj] == 0:
temp[i][j] += 1
if flag:
# 실제 녹이기
day += 1
for i in range(n):
for j in range(m):
if arr[i][j] >= temp[i][j]:
arr[i][j] -= temp[i][j]
else:
arr[i][j] = 0
ice(arr)
return
else:
return print(day)
# 빙산 개수 세기
def ice(arr):
visited = [[0] * m for _ in range(n)]
queue = []
count = 0
p = 0
for a in range(n):
for b in range(m):
if arr[a][b] and visited[a][b] == 0:
count += 1
queue.append(a)
queue.append(b)
visited[a][b] = 1
while p < len(queue):
i = queue[p]
j = queue[p+1]
p += 2
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0 <= ni < n and 0 <= nj < m and visited[ni][nj] == 0 and arr[ni][nj]:
queue.append(ni)
queue.append(nj)
visited[ni][nj] = 1
if count > 1:
return print(day)
return melt(arr)
n, m = list(map(int, sys.stdin.readline().split()))
sea = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
day = 0
melt(sea)코드 변화
1. 빙산의 존재 여부 파악을 위한 flag 추가
-> flag True : 녹이기 코드 실행
-> flag False : 0 출력 반환 (문제에서 전부 녹을 동안 빙산이 두 개 이상으로 분리되지 않으면 0 출력)
틀린 이유
1. 처음부터 빙산이 두 조각 이상인 경우 문제 발생
최종 정답
# 1. 빙산을 줄어들게 하는 함수 -> 인접 바다 개수를 세어 높이 차감
# -> 주의! 방금 녹아 바다가 된 지점은 세지 않음
# -> 녹일 빙산이 없을 때 문제 해결
# 2. 빙산의 개수를 세는 함수 -> BFS로 빙산이 두 개 이상인지 파악
# 3. 두 개 이상이라면 -> 지금까지의 시간 출력 반환
import sys
def melt(arr):
global year
temp = [[0] * m for _ in range(n)] # 녹을 높이 저장
flag = False # 빙산 존재 여부
# 녹을 높이 구하기
for i in range(n):
for j in range(m):
if arr[i][j]:
flag = True # 빙산 존재 여부
# 네 방향 탐사로 바다 수, 녹을 높이 저장
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0 <= ni < n and 0 <= nj < m and arr[ni][nj] == 0:
temp[i][j] += 1
if flag: # 실제 녹이기
year += 1
for i in range(n):
for j in range(m):
if arr[i][j] >= temp[i][j]:
arr[i][j] -= temp[i][j]
else:
arr[i][j] = 0
ice(arr) # 빙산 개수 세기
return
else: # 빙산 없을 시 0 출력
return print(0)
# 빙산 개수 세기
def ice(arr):
visited = [[0] * m for _ in range(n)]
queue = []
count = 0
p = 0 # 시간 효율을 위해 포인터 사용
for a in range(n):
for b in range(m):
if arr[a][b] and visited[a][b] == 0:
count += 1
queue.append(a)
queue.append(b)
visited[a][b] = 1
while p < len(queue): # 네 방향 탐사로 붙어 있는 빙산 방문
i = queue[p]
j = queue[p+1]
p += 2
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0 <= ni < n and 0 <= nj < m and visited[ni][nj] == 0 and arr[ni][nj]:
queue.append(ni)
queue.append(nj)
visited[ni][nj] = 1
if count > 1: # 빙산이 여러 조각이면 시간 출력 반환
return print(year)
return melt(arr) # 빙산이 한 조각이면 melt 함수 실행
n, m = list(map(int, sys.stdin.readline().split()))
sea = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
year = 0
# 처음 주어지는 빙산의 개수 세기
ice(sea)코드 변화
1. melt 함수 실행 전 ice 함수로 빙산의 개수 파악
2. 시간 변수 day -> year 변경 (문제 조건 따라서 바꿈)
반례
| 입력 | 2 2 0 0 0 0 | 4 4 0 0 0 0 0 3 1 0 0 1 3 0 0 0 0 0 | 5 7 0 0 0 0 0 0 0 0 3 3 2 3 3 0 0 4 0 4 0 3 0 0 0 0 0 4 3 0 0 0 0 0 0 0 0 | 5 7 0 0 0 0 0 0 0 0 9 8 9 8 9 0 0 9 8 9 8 9 0 0 9 8 9 8 9 0 0 0 0 0 0 0 0 | 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 7 7 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 9 1 9 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 |
| 출력 | 0 | 1 | 0 | 5 | 0 | 2 |
테스트 케이스가 적어서 반례를 생각해보고, 찾아보는게 도움이 되었음
느낀점
며칠이라도 다시 꾸준히 알고리즘 문제를 푸니까 이전에 풀던 기억들이 돌아오는 것 같다.
주간 주제 외에도 약한 부분을 따로 몇 문제 섞어서 개념 학습을 추가해야겠다.
'알고리즘 > 🥇 골드' 카테고리의 다른 글
| 백준 5430 AC 파이썬 풀이, 반례 (1) | 2023.04.21 |
|---|---|
| 백준 14503 로봇청소기 파이썬 풀이, 반례 (1) | 2023.04.20 |
| 백준 13549 숨바꼭질3 파이썬 풀이, 반례 (0) | 2023.04.19 |
| 백준 7569 토마토 파이썬 풀이 (0) | 2023.04.17 |
| 백준 7576 토마토 파이썬 풀이, 시간초과 해결 (0) | 2023.04.15 |
