백준 문제 풀이

2589 보물섬

from collections import deque

n,m=map(int, input().split())
maps=[]
for i in range(n):
  maps.append(list(input()))

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

def bfs(i,j):
  queue=deque()
  queue.append((i,j))
  visited=[[0]*m for _ in range(n)]
  visited[i][j]=1
  cnt=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=n or ny<0 or ny>=m:
        continue
      elif maps[nx][ny]=='L' and visited[nx][ny]==0:
        visited[nx][ny]=visited[x][y]+1
        cnt=max(cnt,visited[nx][ny])
        queue.append((nx,ny))
  return cnt-1

result=0
for i in range(n):
  for j in range(m):
    if maps[i][j]=='L':
      result=max(result,bfs(i,j))

print(result)

2636 치즈

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

def bfs():
    q = deque([(0, 0)])
    melt = deque([])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                visited[nx][ny] = 1
                if cheeze[nx][ny] == 0:
                    q.append((nx, ny))
                elif cheeze[nx][ny] == 1:
                    melt.append((nx, ny))
                    
    for x, y in melt:
        cheeze[x][y] = 0
    return len(melt)

n, m = map(int, input().split())
cheeze = []
cnt = 0
for i in range(n):
    cheeze.append(list(map(int, input().split())))
    cnt += sum(cheeze[i])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

time = 1
while True:
    visited = [[0] * m for _ in range(n)]
    meltCnt = bfs()
    cnt -= meltCnt
    if cnt == 0:
        print(time, meltCnt, sep='\n')
        break
    time += 1

5427 불

from collections import deque
import sys

input = sys.stdin.readline

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

def bfs():
    cnt = 0
    while q:
        cnt += 1
        while fire and fire[0][2] < cnt:
            x, y, time = fire.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if board[nx][ny] == "." or board[nx][ny] == "@":
                        board[nx][ny] = "*"
                        fire.append((nx, ny, time + 1))

        while q and q[0][2] < cnt:
            x, y, time = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if board[nx][ny] == "." and not visited[nx][ny]:
                        visited[nx][ny] = True
                        q.append((nx, ny, time + 1))
                else:
                    return cnt

    return "IMPOSSIBLE"

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        w, h = map(int, input().split())

        q = deque()
        fire = deque()

        board = []
        visited = [[False] * w for _ in range(h)]
        for i in range(h):
            board.append(list(input().strip()))
            for j in range(w):
                if board[i][j] == "@":
                    visited[i][j] = True
                    q.append((i, j, 0))
                elif board[i][j] == "*":
                    fire.append((i, j, 0))

        print(bfs())

9205 맥주 마시면서 걸어가기

from collections import deque

def bfs():
    q = deque()
    q.append((home_x,home_y))
    while q:
        x,y = q.popleft()
        if abs(x-festival_x) + abs(y-festival_y) <= 1000:
            print('happy')
            return
        for i in range(n):
            if not visited[i]:
                new_x,new_y = graph[i]
                if abs(x-new_x) + abs(y-new_y) <= 1000:
                    visited[i] = 1
                    q.append((new_x,new_y))
    print('sad')
    return

t = int(input())

for _ in range(t):
    n = int(input())
    home_x,home_y = map(int,input().split())
    graph = []
    for _ in range(n):
        x,y = map(int,input().split())
        graph.append((x,y))
    festival_x,festival_y = map(int,input().split())
    visited = [0 for _ in range(n+1)]
    bfs()

13913 숨바꼭질 4

from collections import deque

def bfs():
    q = deque()
    q.append(n)
    while q:
        v = q.popleft()
        if v == k:
            print(visited[v])
            ans = []

            while v != n:
                ans.append(v)
                v = path[v]
            ans.append(n)
            ans.reverse()
            print(' '.join(map(str, ans)))
            return
        for next_step in (v-1, v+1, v*2):
            if 0 <= next_step < MAX and not visited[next_step]:
                visited[next_step] = visited[v] + 1
                q.append(next_step)
                path[next_step] = v

n, k = map(int, input().split())
MAX = 100001
visited = [0] * MAX
path = [0] * MAX
bfs()

17836 공주님을 구해라!

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x, y, dst_x, dst_y, time):
    q = deque([(x, y, time)])
    visited = [[0] * m for _ in range(n)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while q:
        x, y, time = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != 1 and not visited[nx][ny]:
                if nx == dst_x and ny == dst_y:
                    return time+1
                visited[nx][ny] = 1
                q.append((nx, ny, time+1))
    return float('inf')

n, m, t = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(n):
    graph[i] = list(map(int, input().split()))
    if 2 in graph[i]:
        knife = [i, graph[i].index(2)]

not_use_knife = bfs(0, 0, n-1, m-1, 0)

tmp = bfs(0, 0, knife[0], knife[1], 0)
if tmp != float('inf'):
    use_knife = tmp + abs(n-1 - knife[0]) + abs(m-1 - knife[1])
else:
    use_knife = tmp
ans = min(not_use_knife, use_knife)
print(ans if ans <= t else 'Fail')