[구름톤 챌린지 WEEK 3 - 탐색과 동적 프로그래밍] DAY 12. 발전기

DAY 12. 발전기

행렬에서의 효율적 탐색 문제

 

import sys
from collections import deque

n = int(sys.stdin.readline())
dq = deque()

# 인덱스가 넘치는 것을 막기 위해 의미없는 데이터 한줄 늘려줌
arr = [(list(map(int, sys.stdin.readline().split())) + [0]) for i in range(n)]
arr.append([0 for i in range(n + 1)])

dr = [1, -1, 0, 0]
dc = [0, 0, -1, 1]

count = 0
for r in range(n):
    for c in range(n):
        # 0이라면 상관 없음
        if arr[r][c] == 0:
            continue

        # 1이라면 발전소를 설치 후 상하좌우 탐색을 위해 큐에 집어넣음
        count += 1
        dq.append((r,c))
        while dq:
            #큐에서 하나 꺼내오고
            pop_r, pop_c = dq.popleft()
            #꺼내온게 1이라면 0으로 바꾸고 거기서 다시 상하좌우 뻗어
            if arr[pop_r][pop_c] == 1:
                arr[pop_r][pop_c] = 0
                for i in range(4):
                    dq.append((pop_r+dr[i], pop_c+dc[i]))

print(count)

어려워서 알고리즘 스터디원분의 코드를 참고했다.

알고리즘 문제 풀 때 풀리는 문제만 풀다 보니까 내가 완탐을 거의 못푼다는 사실을 깨달았다..

이번 기회에 해설 보고 공부하고, 유형 파악을 해보려 한다.

---

- DFS(깊이 우선 탐색) 풀이

: 방문하는 방향으로 최대한 깊게 파고들어가며 탐색한 후, 돌아오는 풀이

# 코드 맨 위에 추가해줍니다.
import sys
# 재귀 깊이 제한을 100000번으로 늘립니다.
sys.setrecursionlimit(10**5) 

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

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

# 답을 저장할 변수
result = 0

def dfs(i, j):
    # 방문한 위치를 0으로 바꿔 방문 처리를 해줍니다.
    arr[i][j] = 0

    for k in range(4):
        y, x = i + dy[k], j + dx[k]

        # 범위를 벗어나거나, 집이 없는 경우 건너 뜁니다.
        # not은 뒤에 따라오는 True/False를 반대로 뒤집어요.
        # arr[y][x] = 0이면, bool(arr[y][x]) = False입니다.
        # 그러면 not arr[y][x] 의 값은 True가 되죠!
        if y in (-1, N) or x in (-1, N) or not arr[y][x]:
            continue

        # (y, x) 위치로 탐색을 진행합니다.
        dfs(y, x)

# arr 배열을 훝어서 몇 개의 그룹이 있는지 체크할게요.
for i in range(N):
    for j in range(N):
        # 집이 있는 경우, 답에 1을 더하고 인접한 모든 칸을 탐색해 0으로 바꿉니다.
        if arr[i][j]:
            result += 1
            dfs(i, j)

print(result)

재귀로 풀면 재귀 깊이 제한을 풀어도 테스트 케이스를 통과하지 못해 비재귀로 풀어야 한다.

 

- DFS 비재귀 풀이(stack 활용)

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

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

result = 0

def dfs(i, j):
    # 초기 위치인 (i, j)를 넣어서 스택을 생성합니다.
    stack = [(i, j)]

    # 스택에 값이 들어있는 동안 계속 탐색을 진행할게요.
    while stack:
    	# 스택의 맨 끝에 있는 값을 꺼내옵니다.
        y, x = stack.pop()
		
        # 만약 꺼내온 위치가 이미 방문한 지점이라면 건너뛸게요.
        if not arr[y][x]:
            continue
            
        # 처음 방문한다면 방문 처리를 해줍니다.
        arr[y][x] = 0
        
        # 4 방향에 대해 탐색을 진행합니다.
        for k in range(4):
            ny, nx = y + dy[k], x + dx[k]
            
            # 범위 체크 중요합니다!
            if ny in (-1, N) or nx in (-1, N) or not arr[ny][nx]:
                continue
                
            # 건너뛰는 조건을 잘 통과했다면 해당 위치를 스택 끝에 추가해줍니다.
            stack.append((ny, nx))

for i in range(N):
    for j in range(N):
        if arr[i][j]:
       	    result += 1
            dfs(i, j)

print(result)

상하좌우 순서 => 스택 => 우좌하상 순서로 탐색

 

---

- BFS(너비 우선 탐색) 풀이

: 물에 돌멩이를 던지면 그 위치를 중심으로 파문이 퍼져나가는 모양처럼 탐색을 진행하는 알고리즘

= 시작 위치를 중심으로 넓게 퍼져나가며 탐색

step 1
. . . . .
. . . . .
. . # . .
. . . . .
. . . . .

step 2
. . . . .
. . # . .
. # . # .
. . # . .
. . . . .

step 3
. . # . .
. # . # .
# . . . #
. # . # .
. . # . .

step 4
. # . # .
# . . . #
. . . . .
# . . . #
. # . # .

step 5
# . . . #
. . . . .
. . . . .
. . . . .
# . . . #

 

# deque를 가져옵니다.
from collections import deque

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

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

result = 0

# BFS를 구현할게요.
def bfs(i, j):
    # deque를 이용해 큐를 만듭니다. q와 queue는 발음이 큐로 동일해서, 저는 보통 q라고 씁니다.
    q = deque([(i, j)])
	
    # 큐의 내부에 원소가 있는 동안 탐색을 계속 진행합니다.
    while q:
    	# 비재귀 DFS와 달리, 왼쪽에서 값을 꺼냅니다. 먼저 들어간게 먼저 나옵니다!
        y, x = q.popleft()
        
        # 방문한 지점이면 건너뜁니다.
        if not arr[y][x]:
        	continue
            
        # 처음 방문하는 경우 방문 체크를 해주고 탐색을 진행합니다.
        arr[y][x] = 0
        
        for k in range(4):
            ny, nx = y + dy[k], x + dx[k]
            
            # 범위 및 이미 방문했는지 체크!
            if ny in (-1, N) or nx in (-1, N) or not arr[ny][nx]:
            	continue
                
            # 방문하지 않은 위치면 큐에 넣어줍니다.
            q.append((ny, nx))
			
for i in range(N):
    for j in range(N):
    	if arr[i][j]:
       	    result += 1
            bfs(i, j)

print(result)

스택, 큐의 오른쪽에 값을 넣는 것은 동일하지만 스택은 오른쪽에서 꺼내고, 큐는 왼쪽에서 꺼낸다.

 

 

BFS, DFS 너무 어렵다.

제대로 이해해 다시 찾아왔을 때 쉽게 푸는 나를 기대하며 작성한다..