16236

날짜 : 2023. 09. 20

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/16236

 

 

코드

기존 코드(예제 4부터 문제 발생)

import sys
from collections import deque

n = int(sys.stdin.readline())
graph = list()
for _ in range(n): graph.append(list(map(int, sys.stdin.readline().split())))

now_r, now_c = 0, 0  # 상어 위치
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            graph[i][j] = 0 # 수정 안했었음
            now_r, now_c = i, j  # 좌표 설정
            break
    else:
        continue
    break

dx = [-1, 0, 0, 1]  # 상, 좌, 우, 하
dy = [0, -1, 1, 0]

def check(r, c, size):  # 가장 짧은 거리에 있는 먹잇감 체크
    print(r, c, size, "시작")
    visited = [[False] * n for _ in range(n)]
    visited[r][c] = True
    queue = deque()
    queue.append([r, c, 0])
    while queue:
        print(queue)
        x, y, cnt = queue.popleft()
        print(x, y, cnt)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx in range(n) and ny in range(n):
                if not visited[nx][ny]:  # 미방문 지점
                    if 0 < graph[nx][ny] < size:  # 본인보다 작은 물고기 확인
                        graph[nx][ny] = 0  # 먹음
                        return [nx, ny, cnt + 1]
                    elif graph[nx][ny] in (0, size):  # 단순 이동(같은 크기 or 0 )
                        visited[nx][ny] = True  # 방문처리
                        queue.append([nx, ny, cnt+1])
    return [r, c, -1]


now_size = 2
eat = 0
res = 0  # 총 이동량
while True:
    # print(now_r, now_c, res)
    now_r, now_c, move = check(now_r, now_c, now_size)
    if move == -1: break  # 더이상 먹을 물고기가 x
    else:
        res += move  # 총 이동량 갱신
        eat += 1  # 먹은 횟수 갱신
        graph[now_r][now_c] = 0
        if eat == now_size:  # 많이 먹어서 성장
            eat = 0
            now_size += 1
print(res)

 

정답

import sys
from collections import deque

n = int(sys.stdin.readline())
graph = list()
for _ in range(n): graph.append(list(map(int, sys.stdin.readline().split())))

now_r, now_c = 0, 0  # 상어 위치
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            graph[i][j] = 0 # 수정 안했었음
            now_r, now_c = i, j  # 좌표 설정
            break
    else:
        continue
    break

dx = [-1, 0, 0, 1]  # 상, 좌, 우, 하
dy = [0, -1, 1, 0]


def check(r, c, size):
    queue = deque()
    queue.append([r, c, 0])  # 이동 여정 저장
    visited = [[False] * n for _ in range(n)]
    visited[r][c] = True  # 방문여부
    min_dist = [[-1, -1, int(1e9)]]  # 먹잇감 저장
    while queue:
        x, y, cnt = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(n) and ny in range(n): # 범위에 포함
                if not visited[nx][ny]:  # 방문 안했을 때
                    if 0 < graph[nx][ny] < size:  # 먹잇감 포착
                        min_dist.append([nx, ny, cnt+1])  # 저장
                    elif graph[nx][ny] in (0, size):  # 이동만
                        visited[nx][ny] = True  # 방문처리
                        queue.append([nx, ny, cnt+1])
    min_dist.sort(key = lambda x : (x[2], x[0], x[1]))
    return min_dist[0]


now_size = 2
eat = 0
res = 0  # 총 이동량
while True:
    now_r, now_c, move = check(now_r, now_c, now_size)
    if move == int(1e9): break  # 더이상 먹을 물고기가 x
    else:
        res += move  # 총 이동량 갱신
        eat += 1  # 먹은 횟수 갱신
        graph[now_r][now_c] = 0
        if eat == now_size:  # 많이 먹어서 성장
            eat = 0
            now_size += 1
print(res)

 

풀이

- 전반적인 문제 방향성은 BFS였고, 문제에 따라 다양한 조건을 추가해야 했다.

- 우선 아기상어의 좌표를 입력받은 후, BFS를 시작할 위치를 설정한다.(

- 이 또한 9로 되어있기 때문에 해당 좌표값을 0으로 초기화해야 오류를 피할 수 있다.

- 이동할 수 있는 케이스는 상어의 사이즈(size)보다 작거나 같은 경우에만 이동이 가능하다. 그러나 먹잇감을 포착해야 하기 때문에 1부터 (size-1)의 경우의 수와, 이동만 하는 (0, size)의 경우의 수를 나누어 생각한다.

- 먹잇감을 포착했으면 min_dist에 저장하고, 그 이후에 움직이지 않아도 되어 queue에는 여정을 저장하지 않는다.

- 이동만 하는 경우에는 먹잇감을 찾을 때까지 이동해야 했기 때문에 queue에 push한다.

- 그렇게 이동을 마치고 queue의 크기가 0이 되며 자연스레 while문을 탈출하고 최소거리인 최우선순위의 먹잇감의 좌표를 리턴한다.

- 다만 먹잇감이 없을 수 있기 때문에 min_dist에는 거리가 int(1e9)인 케이스를 미리 넣어 엄마상어에게 요청하는 경우의 수를 마련한다.

- check() 함수 이후에 먹잇감을 찾았다면 리턴하는 거리의 값이 int(1e9)가 아닐 것이고, 문제 요구사항처럼 먹은 수를 증가시킴과 동시에 케이스에 따라 상어 사이즈를 키운다.

- 반대로 먹잇감을 찾지 못해 엄마상어에게 도움을 요청하는 경우에는 반복문을 탈출하고 이동거리를 출력한다.

 

 

 

알게된 점

- 문제를 풀이하면서 많은 고민을 한 문제였다. 

- 우선 BFS를 한번만 돌렸다는 점에서 문제가 발생했고, visited도 전역으로 선언했다는 점에서 문제가 발생했다.

- 또 여정과 먹잇감을 저장하는 리스트를 따로 만들지 않아(코드 1) 예제 4에서처럼 동일한 거리지만 중간에 리턴해버리는바람에 우선순위에 밀리는 좌표가 곧바로 다음 차례가 되는 케이스도 발생했다.

- 그리고 자잘자잘하게 실수도 있었는데 아기상어의 좌표를 구한 후 해당 좌표의 데이터를 9에서 0으로 초기화하지 않아 처음 예제를 돌릴때부터 이상한 값이 튀어나오기도 했다.

- 한 2일동안 아침저녁으로 고민하고 코드를 짜고, 챗 GPT 등 다양한 방식으로 공부하면서 조금 고민하는 역량을 키운 것 같다.

- 굉장히 근성을 요하는 문제였지만 유명한 이유가 있는 것 같다.

 

 

참고 사이트

-