[이코테] DFS/BFS_연구소 복습(9.1)

[이코테] DFS/BFS_미로탈출

from collections import deque

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

def bfs(x, y):
	queue = deque()
    queue.append((x, y))
    while queue:
    	x, y = queue.popleft()
    # 현재 위치에서 네 방향으로의 위치 확인
    for i in range(4):
    	nx = x + dx[i]
        ny = x + dy[i]
        # 미로 찾기 공간을 벗어난 경우 무시
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
        	continue
        # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
        if graph[nx][ny] == 1:
        	graph[nx][ny] = graph[x][y] + 1
            queue.append((nx, ny))
     # 가장 오른쪽 아래까지의 최단 거리 반환
     return graph[n - 1][m - 1]
     
print(bfs(0, 0))

[이코테] BFS/DFS_연구소

n, m = map(int, input().split())
data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트

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

# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

# 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                # 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
                temp[nx][ny] = 2
                virus(nx, ny)

# 현재 맵에서 안전 영역의 크기 계산하는 메서드
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

# 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산
def dfs(count):
    global result
    # 울타리가 3개 설치된 경우
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        # 각 바이러스의 위치에서 전파 진행
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        # 안전 영역의 최대값 계산
        result = max(result, get_score())
        return
    # 빈 공간에 울타리를 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1

dfs(0)
print(result)

다른풀이 1

1) 바이러스는 '2' 이며 상하좌우의 인접한 빈칸(0)으로만 이동이 가능하기 때문에

• 먼저 '2'인 칸들을 모두 큐에 넣어준 후에,
• BFS(너비우선탐색)을 통해 큐에서 하나씩 꺼내 확장시키는 방식
  (2인 칸에서 시작하여 주변의 0인 칸들을 2로 만드는 방식)

2) 이 때, 어디에 벽을 세워야 최댓값이 나올지는 알 수 없기 때문에 벽을 세울 수 있는 모든 경우의 수에 대해 수행 필요

• 따라서, (1, 1) 칸 부터 (n, m)칸 까지 중 빈칸을 순서대로 하나씩 3개 선택하여
• 벽을 세우고 BFS를 수행한 후 벽을 지우고
• 그 다음칸에 대해 다시 벽을 세우고 BFS를 수행하고 벽을 지우는 방식을 반복해야 한다.

즉, 백트래킹 방식을 이용해 3개의 벽을 모든 칸에 세워본다.

3) 이렇게 진행하면서 최댓값을 저장한 후, 모든 탐색이 끝난 후 최댓값을 출력

from collections import deque
import copy

def bfs():
    queue = deque()
    tmp_graph = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                queue.append((i, j))

    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
            if tmp_graph[nx][ny] == 0:
                tmp_graph[nx][ny] = 2
                queue.append((nx, ny))

    global answer
    cnt = 0

    for i in range(n):
        cnt += tmp_graph[i].count(0)

    answer = max(answer, cnt)


def makeWall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makeWall(cnt+1)
                graph[i][j] = 0

n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

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

answer = 0
makeWall(0)
print(answer)

다른풀이 2

import sys
import copy
from collections import deque

input = sys.stdin.readline

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

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = 0
q = deque()

def bfs():
    global ans
    w = copy.deepcopy(arr)
    for i in range(N):
        for j in range(M):
            if w[i][j]==2:
                q.append([i,j])

    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:
                if w[nx][ny]==0:
                    w[nx][ny] = 2
                    q.append([nx,ny])
    cnt = 0
    for i in w:
        cnt+=i.count(0)
    ans = max(ans,cnt)

def wall(x):
    if x==3:
        bfs()
        return
    for i in range(N):
        for j in range(M):
            if arr[i][j]==0:
                arr[i][j]=1
                wall(x+1)
                arr[i][j]=0

wall(0)
print(ans)

정리할 부분

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

    # 현재 위치에서 네 방향으로의 위치 확인
    for i in range(4):
    	nx = x + dx[i]
        ny = x + dy[i]
        # 미로 찾기 공간을 벗어난 경우 무시
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
        	continue        
        # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
        if graph[nx][ny] == 1:
        	graph[nx][ny] = graph[x][y] + 1
            queue.append((nx, ny))

2)

# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                # 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
                temp[nx][ny] = 2
                virus(nx, ny)

링크텍스트