99클럽 코테 스터디 12일차 TIL - BFS (백준7569- 토마토)

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

• 오늘의 학습 키워드 : BFS

1. BFS로 최소 일수 계산
2. 초기 상태에서 익은 토마토를 큐에 넣기
3. 6방향 탐색
문제의 조건에 따라 위, 아래, 왼쪽, 오른쪽, 앞, 뒤의 6방향
4. 최대 일수 갱신
BFS를 진행하면서 days 변수를 매 단계 갱신하며, 모든 토마토가 익을 때까지 걸린 최대 일수를 기록
최종적으로 모든 토마토가 익었을 때 max_days가 최소 일수
5. 최종 상태 체크(토마토가 모두 익지 않았는지 익었는지 체크 필요)
- 만약 남아있다면, -1을 출력하고 종료하여 불가능한 경우를 처리
- 반면 , 모든 토마토가 익었다면, max_days를 출력합니다.

• 공부한 내용
  

  import sys
  from collections import deque
  INF = int(1e9)  # 무한대를 나타내는 값으로, 사용할 필요는 없지만, 코드 상에서 가독성을 위해 남겨둠
  
  # 입력 받기
  M, N, H = map(int, sys.stdin.readline().strip().split())  # 가로 M, 세로 N, 높이 H
  graph = [[] for _ in range(H)]  # 3차원 배열로 창고를 표현하기 위해 높이 H만큼 리스트 생성
  queue = deque()  # BFS를 위한 큐 초기화
  
  # 창고 상태 입력 및 초기 익은 토마토 위치 큐에 추가
  for h in range(H):  # 각 층
      for n in range(N):  # 각 행
          graph[h].append(list(map(int, sys.stdin.readline().strip().split())))  # 각 행 입력 받아 2차원 리스트로 저장
          for m in range(M):  # 각 열
              if graph[h][n][m] == 1:  # 익은 토마토라면
                  queue.append((h, n, m, 0))  # 큐에 추가하며 (층, 행, 열, 일수 0)로 저장
  
  # BFS 탐색 방향 설정 (6방향: 위, 아래, 왼쪽, 오른쪽, 앞, 뒤)
  move = [(0, 0, 1), (0, 0, -1), (0, 1, 0), (0, -1, 0), (1, 0, 0), (-1, 0, 0)]
  max_days = 0  # 최대 일수를 저장할 변수
  
  # BFS 시작
  while queue:
      nodeh, noden, nodem, days = queue.popleft()  # 현재 토마토 위치와 걸린 일수 꺼내기
      max_days = max(max_days, days)  # 최대 일수를 갱신
  
      # 6방향으로 탐색
      for dh, dm, dn in move:
          # 인접한 위치 계산
          nh, nn, nm = nodeh + dh, noden + dn, nodem + dm
          # 범위 내에 있고, 익지 않은 토마토가 있을 경우
          if 0 <= nh < H and 0 <= nn < N and 0 <= nm < M:
              if graph[nh][nn][nm] == 0:  # 익지 않은 토마토일 경우
                  graph[nh][nn][nm] = 1  # 익은 토마토로 변경
                  queue.append((nh, nn, nm, days + 1))  # 새 위치와 일수 증가시켜 큐에 추가
  
  # 모든 토마토가 익었는지 확인
  for h in range(H):
      for n in range(N):
          if 0 in graph[h][n]:  # 익지 않은 토마토가 남아있다면
              print(-1)  # -1 출력 후 프로그램 종료
              exit()
  
  # 모든 토마토가 익었다면 최대 일수를 출력
  print(max_days)

• 오늘의 회고
  • 요며칠 바빠서 문제만 풀고 풀이를 잘 쓰지 않았는데 오랜만에 다시 써본다..
  • 요며칠 백준 문제는 나름 골드 문제들이 나와서 이제 이제까지 배운 BFS, DFS를 좀더 응용해서 어찌하면 좋을까? 생각하는 풀이를 생각하게 된다? 그런 느낌쓰..
    그래서 좀 머리를 더 쓰는 느낌이여서 좋았다 그말을 하고 싶었다.
    여기서 이제 좀더 발전할라면 다른 사람 코드도 참조하고 이것저것 할게 많은데 요 며칠 바쁘고 이러니깐 그럴만한 여유가 없어서 자꾸만 미루게 되네..
    내일은 좀더 아자아자 힘내서 해봐야징