BFS - 음식물 피하기/토마토/숨바꼭질/안전영역

deque 사용하기

from collections import deque

• queue = deque()
• curX, curY = queue.popleft()

1743 음식물 피하기

from collections import deque

dx = [0, 1, 0 ,-1]
dy = [-1, 0, 1, 0]
mx = 0
queue = deque()
res = 0
size = 0

def bfs(i, j):
    global size
    queue.append([i,j])
    vis[i][j] = 1
    size += 1
    
    while queue:
        curX, curY = queue.popleft()
        for dir in range(4):
            nx = curX + dx[dir]
            ny = curY + dy[dir]
            if nx < 0 or nx >= n or ny <0 or ny >= m:
                continue;
            if board[nx][ny] == 0 or vis[nx][ny] > 0:
                continue;
            queue.append([nx,ny])
            vis[nx][ny] = 1
            size += 1


n, m, k = map(int, input().split()) # 세로 가로 음식물개수

board = [[0] * m for _ in range(n)]
vis = [[0] * m for _ in range(n)]

for _ in range(k):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1;


for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            size = 0
            bfs(i,j)
            res = max(res, size)
print(res)

2차원 리스트 초기화

board = [[0] * m for _ in range(n)]  # n:세로, m:가로
vis = [[0] * m for _ in range(n)]

dfs 함수안에서 global을 안해주면 오류가 난다. global 키워드를 공부해야겠다

---

7576 토마토

from collections import deque

m,n = map(int, input().split())
s=[]
queue = deque()
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
res = 0

def bfs():
    while queue:
        curX, curY = queue.popleft()
        
        for dir in range(4):
            nx = curX + dx[dir]
            ny = curY + dy[dir]
            if 0 <= nx < n and 0 <= ny < m and s[nx][ny] == 0:
                s[nx][ny] = s[curX][curY] + 1;
                queue.append([nx,ny])


for i in range(n):
    s.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if s[i][j] == 1:
            queue.append([i,j])
bfs()

for i in s:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
        res = max(res, j)
print(res-1)
        

이부분이 헷갈렸는데 s가 2차원 리스트를 사용한다는걸 기억하자

for i in s:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
        res = max(res, j)

1697 숨바꼭질

from collections import deque

queue = deque()

dist = [0] * 100005
n, k = map(int, input().split())
dist[n] = 1;
queue.append(n)

while queue:
    cur = queue.popleft()
    for nx in (cur-1, cur+1, cur*2):
        if nx >= 0 and nx <= 100000 and not dist[nx]:
            queue.append(nx)
            dist[nx] = dist[cur]+1
    if dist[k]:
        break;

    
print(dist[k]-1)

간단하게 for문 실행하는 방법!

for nx in (cur-1, cur+1, cur*2):
        if nx >= 0 and nx <= 100000 and not dist[nx]:
            queue.append(nx)
            dist[nx] = dist[cur]+1

간단하게 1차원 리스트 생성하기

dist = [0] * 10

>>> dist = [0] * 10
>>> dist
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

2468 안전영역

from collections import deque
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
queue = deque()
board = []
res = 0
safe = 0

def bfs(i,j, rain):
    global res, safe
    safe += 1
    queue.append([i,j])
    while queue:
        curX, curY = queue.popleft()
        for dir in range(4):
            nx = curX+dx[dir]
            ny = curY+dy[dir]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if board[nx][ny] > rain and vis[nx][ny] == 0:
                queue.append([nx,ny])
                vis[nx][ny] = 1

n = int(input())
for _ in range(n):
    board.append(list(map(int, input().split())))


for rain in range(1, 101):
    vis = [[0]*n for _ in range(n)]
    safe = 0
    for i in range(0,n):
        for j in range(0,n):
            if board[i][j] > rain and vis[i][j] == 0:
                bfs(i,j, rain)
    res = max(res, safe)
                
if res == 0:
    print(1)
else:
    print(res)
                

• 2차원 리스트 초기화

vis = [[0]*n for _ in range(n)]