[알고리즘] BFS - 백준 2589 2636 5427 9205 13913 17836

 

2589 보물섬

 

import sys
from collections import deque
 
input = sys.stdin.readline
 
s, g = map(int, input().split())
maps = []
for _ in range(s):
    maps.append(list(input()))
    
dxdy = [(0,1), (0,-1), (1,0), (-1,0)]
 
def bfs(i,j):
    q = deque()
    q.append((i, j))
    visited = [[False]* g for _ in range(s)]
    visited[i][j] = 1
    length = 0
            
    while q:
        x, y = q.popleft()
        for i in range(4):
            dx = dxdy[i][0]
            dy = dxdy[i][1]
            
            nx = x + dx
            ny = y + dy
            
            if nx < 0 or nx >= s or ny < 0 or ny >= g:
                continue
            elif maps[nx][ny] == 'L' and visited[nx][ny] == False:
                visited[nx][ny] = visited[x][y] + 1
                length = max(length, visited[nx][ny])
                q.append((nx, ny))
                
    return length - 1
    
ans = 0
 
for i in range(s):
    for j in range(g):
        if maps[i][j] == 'L':
            ans = max(ans, bfs(i, j))
            
print(ans)

 

2636 치즈

import sys
from collections import deque
 
input = sys.stdin.readline
 
s, g = map(int, input().split())
 
che = []
cnt = 0
dxdy = [(0,1), (0,-1), (1,0), (-1,0)]
 
for i in range(s):
    che.append(list(map(int, input().split())))
    cnt += sum(che[i])
    
def bfs():
    q = deque()
    q.append((0, 0))
    bye = deque()
    visited = [[False]*g for _ in range(s)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            dx = dxdy[i][0]
            dy = dxdy[i][1]
            nx = x + dx
            ny = y + dy
            if 0 <= nx < s and 0 <= ny < g and not visited[nx][ny]:
                visited[nx][ny] = 1
                if che[nx][ny] == 0:
                    q.append((nx, ny))
                elif che[nx][ny] == 1:
                    bye.append((nx, ny))
                    
    for x, y in bye:
        che[x][y] = 0
    return len(bye)
 
time = 1
 
while True:
    byecnt = bfs()
    cnt -= byecnt
    if cnt == 0:
        print(time)
        print(byecnt)
        break
    time += 1

 

5427 불

import sys
from collections import deque
 
input = sys.stdin.readline
 
dx = [1,0,-1,0]
dy = [0,1,0,-1]
 
def bfs():
    time = 0
    while q:
        time += 1
        while fire and fire[0][2] < time:
            x, y, t = fire.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<h and 0<=ny<w:
                    if maps[nx][ny] == '.' or maps[nx][ny] == '@':
                        maps[nx][ny] = '*'
                        fire.append((nx, ny, t + 1))
                        
                        
        while q and q[0][2] < time:
            x, y, t = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<h and 0<=ny<w:
                    if maps[nx][ny] == '.' and not visited[nx][ny]:
                        visited[nx][ny] = True
                        q.append((nx, ny, t + 1))
                        
                else:
                    return time 
                
    return 'IMPOSSIBLE'               
                                    
 
 
T = int(input())
 
for _ in range(T):
    w, h = map(int, input().split())
    
    q = deque() # 나
    fire = deque()  # 불
    
    maps = []
    visited = [[False]*w for _ in range(h)]
    for i in range(h):
        maps.append(list(input()))
        for j in range(w):
            if maps[i][j] == '@':
                visited[i][j] = True
                q.append((i,j,0))
            elif maps[i][j] == '*':
                fire.append((i,j,0))
                
    print(bfs())

 

9205 맥주 마시면서 걸어가기

import sys
from collections import deque
 
input = sys.stdin.readline
 
def bfs():
    q = deque()
    q.append([start[0], start[1]])
    while q:
        x, y = q.popleft()
        if abs(x-fe[0]) + abs(y-fe[1]) <= 1000:
            print('happy')
            return
        for i in range(n):
            if not visited[i]:
                newx, newy = shop[i]
                if abs(x-newx) + abs(y-newy) <= 1000:
                    q.append([newx, newy])
                    visited[i] = True
    print('sad')
    return
 
t = int(input())
 
for _ in range(t):
    n = int(input())
    start = [int(x) for x in input().split()]
    shop = []
    for j in range(n):
        x, y = map(int, input().split())
        shop.append([x, y])
    fe = [int(x) for x in input().split()]
    visited = [False for _ in range(n+1)]
    bfs()

 

13913 숨바꼭질 4

 

import sys
from collections import deque
 
input = sys.stdin.readline
 
n, k = map(int, input().split())
 
visited = [-1] * 100001
 
path = []
 
def bfs(start, target):
    q = deque()
    q.append((n, 0))
    visited[start] = start
    while q:
        cur, time = q.popleft()
        if cur == target:
            idx = cur
            while idx != start:
                path.append(idx)
                idx = visited[idx]
            path.append(start)
            return time
        
        if cur + 1 < 100001 and visited[cur + 1] == -1:
            q.append((cur+1, time + 1))
            visited[cur+1] = cur
        if cur - 1 >= 0 and visited[cur-1] == -1:
            q.append((cur-1, time + 1))
            visited[cur-1] = cur
        if cur*2 < 100001 and visited[cur*2] == -1:
            q.append((cur*2, time + 1))
            visited[cur*2] = cur
            
print(bfs(n, k))
print(*path[::-1])

 

 

17836 공주님을 구해라!

 

import sys
from collections import deque
 
input = sys.stdin.readline
INF = int(1e9)
n, m, t = map(int, input().split())
maps = []
 
for _ in range(n):
    maps.append(list(map(int, input().split())))
    
visited = [[False for _ in range(m)] for _ in range(n)]
 
dxdy =[[1,0], [-1,0], [0,1], [0,-1]]
res = INF
 
 
q = deque()
q.append((0,0,0))
visited[0][0] = True
while q:
    x, y, d = q.popleft()
        
    if x == n-1 and y == m-1:
        res = min(res, d)
        break
    if d+1 > t:
        break
        
    for i in dxdy:
        nx, ny = i[0] + x, i[1] + y
        if (-1<nx<n and -1<ny<m) and not visited[nx][ny]:
            if not maps[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny, d+1))
            elif maps[nx][ny] == 1:
                continue
            elif maps[nx][ny] == 2:
                tmp = d + 1
                tmp += abs(n-1-nx) + abs(m-1-ny)
                visited[nx][ny] = True
                    
                if tmp <= t:
                    res = tmp
 
if res > t:
    print('Fail')
else:
    print(res)