🥑 생각보다 까다로운 걸,,?
처음에는 오 얘는 bfs구나,, 하고 풀었다.
얼추 값은 나오는데 답은 아니다.
bfs + 방문 체크 방식으로 풀었다.
뭔가 요기서 에러만 고치면 될 것 같지만~~~~
생각보다 코드가 매우 길어졌고 길어져서
고냥 다시 코드를 짰다.
2차원 배열을 만들지 않고 그냥 리스트 형식을 이용했다!
def move():
## 원래의 방향
dir = [(0,0), (-1, 0), (1, 0), (0, -1), (0, 1)]
## dir의 반대 방향
reverse_dir = [0, 2, 1, 4, 3]
# 방문 체크
check = {}
## 군집의 갯수만큼 반복
for th in range(k):
group = arr[th]
r, c, cnt, d = group
## 미생물이 없다면 패스
if cnt == 0: continue
## 군집에 새로운 위치를 할당
nr = r + dir[d][0]
nc = c + dir[d][1]
group[0], group[1] = nr, nc
## 약품 처리가 된 곳이라면 미생물의 수를 반으로 줄이고, 방향을 반대 방향으로 변경
if nr == 0 or nr == n-1 or nc == 0 or nc == n-1:
group[2] //= 2
group[3] = reverse_dir[d]
## 방문한 적이 없다면 방문 쳌
if (nr, nc) not in check:
check[(nr,nc)] = (th, cnt)
continue
## 방문한 적이 있다면 이미 담겨 있는 값을 가져오기
next_th, next_cnt = check[(nr, nc)]
## 현재의 미생물 수가 더 많다면
## 현재 미생물에 이미 위치에 담겨있는 미생물 수를 더하고
## 이전에 담겨 있던 미생물 수를 0으로 초기화
if cnt > next_cnt:
group[2] += arr[next_th][2]
# group[2] += next_cnt 이거는 틀림!!!!! 왜?? --- 같은 위치에 모인 값 중 최대값을 뜻하는 것이니 틀림
check[(nr, nc)] = (th, cnt) ## 최대값 갱신
arr[next_th][2] = 0 ## 미생물 수가 합쳐졌으니 얘는 초기화
else:
arr[next_th][2] += cnt ## 이미 담겨있는 값이 더 크다면 거기에다 현재 미생물 수를 더해줌
group[2] = 0 ## 더해주고 나서 현재 군집의 미생물 수를 0으로 초기화
for tc in range(1, int(input())+1):
n, m, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(k)]
## 주어진 시간만큼 for문을 돌기
for _ in range(m):
move()
result = 0
for i in range(k):
result += arr[i][2]
print('#{} {}'.format(tc, result))
가장 헷갈렸던 부분은 저기 (0,1)과 (1,1)사이다.
군집의 갯수만큼 반복문을 돌고 변경된 값을 만들어둔 표에다가 넣으면 된다고 생각했다. !! 그런데 그렇게 되면 저 3이 밑에 있는 7과 합쳐져서 10이라는 값이 나온다.
원래라면 3이 밑으로 7이 위로 가야한다.
그래서 이 문제의 핵심은 방문 체크라고 생각하는 바이다 .🥦
bfs로 해보려다가 4일 동안 고치고 들여다보다 리스트 형식으로 클리어했다,,,!
갹