• 링크 : https://www.acmicpc.net/problem/17086

---

메모

• N x M, 한 칸에 상어 최대 1마리

  • 0 = 빈칸
  • 1 = 상어

• 이동 기준은 대각선 포함쓰... 가운데 제외 총 8개

• 구해야 하는 것 : 안전 거리의 최댓값

• 브루트폴스로 시작해서 그 loop안에 bfs함수 돌리는데

  • bfs()에서 False일 때만 탐색해서 중복탐색 방지하고
  • nx의 그래프 값이 1이면 bfs종료하고 이전 n의 그래프값을 리턴해서 result.append()
  • 최종 맨 마지막에 max(result)하면 될라나>

---

• 내가 처음에 생각한건 브루트폴스로 시작해서
  • BFS()진행하면서 상어 처음 발견하면 걔 거리(이전위치의) return해서 append()해주고
  • 마지막에 max하면 되는거 아닌가?
    • max하면 되는게, 맨 처음에 가장 가까운 애 찾은경우 바로 exit()하니까
    • 가장 가까운 애 목록 중에서 최댓값을 출력하는 거임
• 혹시 안되면 이거 토마토랑 같은 문제??????? => 맞았다 토마토였따ㅠㅠ
  • 시작할 때 시작 상어 위치 다 큐에 넣어주고 bfs돌리는???

---

첫 실패 코드

''' 1회차 '''
from collections import deque

def bfs(init_y,init_x,graph,visit,n, m):
    que = deque()
    que.append((init_y,init_x))
    visit[init_y][init_x] = True
    
    #    좌측 3개, 중앙 2개, 우측 3개
    dy = [-1, 0, 1, -1, 1, -1, 0, 1]
    dx = [-1, -1, -1, 0, 0, 1, 1, 1]
    #dx = (-1, -1, -1, 0, 1, 1, 1, 0)
    #dy = (-1, 0, 1, 1, 1, 0, -1, -1)
    
    while que:
        y, x = que.popleft()
        
        for nextp in range(8):
            ny = y + dy[nextp]
            nx = x + dx[nextp]
            #print(ny, nx)
            #print(visit[ny][nx])
            
            # 방문하지 않고, 범위 안에 있는 위치만
            if 0<= ny < n and 0 <= nx < m and visit[ny][nx] == False:
                #print(y, x, "-> go [", ny, nx, "]", que)
                
                if graph[ny][nx] == 1:
                    #print("y,x=", y,x, "+",dy[nextp], dx[nextp], "ny,nx=",ny,nx)
                    return graph[y][x]
                
                visit[ny][nx] = True
                
                graph[ny][nx] = graph[y][x] + 1
                que.append((ny,nx))
    return 0

n, m = map(int,input().split())
#graph = [list(map(int, input().split())) for _ in range(n)]
graph = [[0, 0, 1, 0], [0, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1]]
#graph = [[0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]]

#visit = [[False]*m]*n5 
visit = [[-1] * m for _ in range(n)]
answer = []

for y in range(n):
    for x in range(m):
        if graph[y][x] == 1:            
            answer.append(bfs(y,x,graph,visit,n, m))
            visit = [[False]*m]*n
            
print(max(answer))
print(answer)
print()
for i in graph:
    print(i)

---

실패이유 - 다시 풀어보자ㅜ

• 첨에 생각한 아이디어는 맞았으나, 몇 가지 놓쳤다
• 1. 토마토랑 같은거였다. 처음에 상어위치 다 큐에 넣어줘야함
• 2. graph로만 하지 말고 별도의 그래프 새로 만들어서 수행하는 방식 인지해야하고,
• 3. max(answer, visit[ny][nx]) <--- 이거 자주 애용하자

답이긴 한데 내가 원한 방식 아님

''' 답지 코드 참고 '''
from collections import deque

n, m = map(int,input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
#graph = [[0, 0, 1, 0], [0, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1]]
#graph = [[0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]]

#visit = [[-1]*m]*n           #<---------------이러면 답이 틀림
visit = [[-1] * m for _ in range(n)]    #<----이래야 맞음 Why????

answer = 0
que = deque()

# (매우중요) 토마토와 똑같이!!! 시작점 다 넣어줌
for y in range(n):
    for x in range(m):
        if graph[y][x] == 1:
            visit[y][x] = 0
            que.append((y,x))    # <-- 토마토처럼 해줘서 max(ans, visit)이 가능했던 것!

#    좌측 3개, 중앙 2개, 우측 3개
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
dx = [-1, -1, -1, 0, 0, 1, 1, 1]


# (매우중요) graph를 안쓰고 별도의 visit 횟수 count
while que:
    y, x = que.popleft()

    for nextp in range(8):
        ny = y + dy[nextp]
        nx = x + dx[nextp]
        
        # 한번도 방문하지 않고, 범위 안에 있는 위치만
        if 0<= ny < n and 0 <= nx < m and visit[ny][nx] == -1:
            visit[ny][nx] = visit[y][x] + 1

            answer = max(answer, visit[ny][nx])   # (매우중요) 바로바로 비교
            que.append((ny,nx))
                
print(answer)

내가 원한 방식 아래 링크 (나중에 파악해보기)

• 내가 풀려고 했던 방식이랑 비슷한데, 위 솔루션이랑 짬뽕된 방식임
• 결론 = 토마토
• 링크 : https://baejinsoo.github.io/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EB%AC%B8%EC%A0%9C%ED%92%80%EA%B8%B0/BOJ_17086/