백준_17086 (아기상어2_BFS - 다시 풀어볼것)

RostoryT·2022년 6월 18일

BFS 백준

BFS DFS

목록 보기

15/24

링크 : 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. 토마토랑 같은거였다. 처음에 상어위치 다 큐에 넣어줘야함
1. graph로만 하지 말고 별도의 그래프 새로 만들어서 수행하는 방식 인지해야하고,
1. 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)