문제 설명
https://www.acmicpc.net/problem/18405
<입력>
<출력>
<예시>
나의 풀이
Solution 1
'문제에서 요구하는 게 맵 전체도 아니고, 단순 바이러스의 종류만 출력하라는 건데, 그럼 단순 거리 계산만 하면 되는 것 아닌가?'
| 메모리 | 29452 KB |
|---|---|
| 시간 | 96 ms |
# 입력
n, k = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
s, x, y = map(int, input().split())
def distance(nx, ny):
return abs(nx-x+1) + abs(ny-y+1)
result = dict()
for i in range(k):
result[i+1] = 2*n
for i in range(n):
for j in range(n):
if graph[i][j] != 0:
result[graph[i][j]] = min(result[graph[i][j]], distance(i, j))
print(result)
for key in result.keys():
result[key] -= s
print(result)
# value들이 전부 +면(s가 너무 작아 바이러스가 안 퍼졌다면) 0 출력, 아니면 value 기준으로 sort한 것 중 제일 앞에 거 출력
is_safe = True
for value in result.values():
if value <= 0:
is_safe = False
break
if is_safe == True:
print(0)
else:
result = sorted(result.items(), key=lambda x: x[1])
print(result[0][0])Solution 2
문제에서 요구하는 게 쉬워서 Solution 1 처럼 풀 수는 있으나, 혹시 맵 전체를 요구했다면? 시간 s 만큼 루프를 돌면서 맵을 업데이트 해보는 방법은 어떤가? 시간이 오래 걸릴 것 같기도 하지만...(역시 효율은 쓰레기였다. BFS 알고리즘이 왜 존재하는 지 알게 되는 코드이다.)
생각한 원리는 이렇다.
1. 전부 0 값으로 초기화된 n*n 크기의 임시 맵을 만든다.
2-1. 2차원 리스트 값 하나하나를 돌면서 그 값이 0 이라면 근접 4방향에 바이러스가 있는 지 체크한다.
2-2. 없으면 걍 넘어가는데, 하나라도 있으면 제일 작은 거를 임시 맵에 넣는다.
3. n*n만큼을 다 돌아 임시 맵이 완성되면, 원래 맵과 임시 맵을 행렬합한다.
4. 위를 s만큼 반복
| 메모리 | 215368 KB |
|---|---|
| 시간 | 2888 ms |
시간 복잡도 : O(s*(N^3 + N^2))
(Python3로 제출하면 시간 초과가 뜬다. 위 결과는 PyPy3 로 제출했을 때의 결과)
# 입력은 생략
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def append_candidates(x, y): # O(4)
temp = []
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if not(nx > n-1 or nx < 0 or ny > n-1 or ny < 0):
if graph[nx][ny] != 0:
temp.append(graph[nx][ny])
return temp
def sumMatrix(A,B): # O(N^2)
for i in range(len(A)) :
for j in range(len(A[0])):
A[i][j] += B[i][j]
return A
def update(graph): # O(N^3 + N^2)
graph_0 = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if graph[i][j] == 0:
temp = append_candidates(i, j)
if len(temp) == 0:
continue
else:
graph_0[i][j] = min(temp) # O(N)
del(temp)
sumMatrix(graph, graph_0)
del(graph_0)
while s > 0: # O(s*(N^3 + N^2))
update(graph)
s -= 1
print(graph[x-1][y-1])다른 사람 풀이
정석대로 BFS를 이용한 풀이인데, 나는 구현이 잘 되지 않았다. 이 사람의 원리는 이렇다.
1. 맵의 바이러스 정보(종류, x좌표, y좌표 집합)만 새로 리스트에 저장 후 정렬한다.(작은 숫자가 앞에 오게끔)
2. 먼저 큐에 바이러스 리스트를 넣고, 큐가 빌 때까지 while 문을 돌린다.(s 시간에 멈춰야 하기 때문에 몇 번 돌았는 지 카운트 후 s 시간에 break)
3. 바이러스를 하나씩 큐에서 꺼내 그 바이러스의 주변을 감염시킨다.(맵의 해당 좌표를 해당 바이러스 종류로 업데이트 한다)(그 주변이 0일 경우에만)
4. 큐에 새로 감염된 좌표를 업데이트 한다.
ex) q = [
1,1,1,...,2,2,2,....3,3,3,....4,4,4....1,1,1,....2,2,2,...](1~4까지가 한 페이즈. 한 페이즈 다 돌면 1초 지난 거임)
| 메모리 | 32804 KB |
|---|---|
| 시간 | 204 ms |
from collections import deque
N, K = map(int, input().split())
graph = []
virus = []
for i in range(N):
graph.append(list(map(int, input().split())))
for j in range(N):
if graph[i][j] != 0:
virus.append(((graph[i][j], i, j)))
S, X, Y = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(s, X, Y):
q = deque(virus)
count = 0
while q:
if count == s:
break
for _ in range(len(q)):
prev, x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if graph[nx][ny] == 0:
graph[nx][ny] = graph[x][y]
q.append((graph[nx][ny], nx, ny))
count += 1
# for i in range(N):
# print(graph[i])
# print()
return graph[X-1][Y-1]
virus.sort()
print(bfs(S, X, Y))느낀 점
BFS 문제인 것을 알았지만, 처음에 구현에 엄두가 나지 않았다
그래서 꼼수 써서 s, x, y 가 처음부터 주어지기 때문에 단순 거리 계산만 하면 된다는 생각에 그렇게 구현해보았다.
그랬더니 해당 문제 파이썬 한정 랭커가 되어버렸다! 재밌는 경험이었다.
그래도 정석대로는 결국 풀지 못했기에 유감을 표하는 바이다.
아 그리고, 다음의 두 가지 경우에서,
arr1 = [0 * n for _ in range(n)]
arr2 = [[0] * n for _ in range(n)]의도한 바 대로 하려면 arr2가 맞다.
No Excuses