9/24 개인 문제 풀이 - 1

17086번: 아기 상어 2

import sys
from collections import deque
from copy import deepcopy

input = sys.stdin.readline

def bfs(i, j):
  temp = deepcopy(graph)

  dy = [1, -1, 0, 0, 1, -1, 1, -1]
  dx = [0, 0, 1, -1, 1, -1, -1, 1]

  if temp[i][j] == 1:
    return 0

  dq = deque()
  dq.append((i, j))

  while dq:
    v = dq.popleft()
    num = temp[v[0]][v[1]]

    for i in range(8):
      ny = v[0] + dy[i]
      nx = v[1] + dx[i]

      if ny < 0 or nx < 0 or ny > N - 1 or nx > M - 1 or temp[ny][nx] < 0:
        continue

      if temp[ny][nx] == 1:
        return abs(num - 1)

      dq.append((ny, nx))
      temp[ny][nx] = num - 1

  return -1

graph = []
N, M = map(int, input().split())

for _ in range(N):
  myList = list(map(int, input().split()))
  graph.append(myList)

safeDistance = 0

for i in range(N):
  for j in range(M):
    v = bfs(i, j)
    if safeDistance < v:
      safeDistance = v

print(safeDistance)

대각선으로도 움직일 수 있다는 것이 신박한 문제였담

bfs 연습하려고 풀었다.

다른 사람들 풀이를 보니 역발상의 중요성을 알았다

상어로 부터 시작해서 최대거리를 찾는 풀이였다.

신박했다.

9/24 개인 문제 풀이 - 2

21736번: 헌내기는 친구가 필요해

import sys
from collections import deque

input = sys.stdin.readline

def bfs(i, j):
  cnt = 0

  dy = [1, -1, 0, 0]
  dx = [0, 0, 1, -1]

  dq = deque()
  dq.append((i, j))

  while dq:
    v = dq.popleft()
    y = v[0]
    x = v[1]

    for i in range(4):
      ny = y + dy[i]
      nx = x + dx[i]

      if ny < 0 or nx < 0 or ny > N - 1 or nx > M - 1 or graph[ny][
          nx] == 'V' or graph[ny][nx] == 'X':
        continue

      dq.append((ny, nx))
      if graph[ny][nx] == 'P':
        cnt += 1
      graph[ny][nx] = 'V'
  return cnt

N, M = map(int, input().split())
graph = []

for _ in range(N):
  str = input()
  myList = []
  for ch in str:
    if ch != '\\n':
      myList.append(ch)
  graph.append(myList)

for i in range(N):
  for j in range(M):
    if graph[i][j] == 'I':
      pos = (i, j)

result = bfs(pos[0], pos[1])

if result != 0:
  print(result)
else:
  print('TT')

bfs 연습 햐려고 또 풀었다. 문제 제목도 다음에 들었다

이제 bfs는 바로바로 써지는 것 같다 다음은 다익스트라를 연습해야겠다