14716번: 현수막

 

 

 

 

 

풀이

 

dfs와 bfs로 풀 수 있는 문제 입니다.

 

dfs

...

아직 방문하지 않은 graph[i][j]가 1인곳에서 dfs을 호출하고 graph[x][y] = 0 으로 방문처리 해줍니다.

 

상,하,좌,우 그리고 대각선에 대한 다음위치를 특정해주고 graph[nx][ny] == 1 이라면 dfs를 재호출 합니다.

 

주위에 1이 없다면 글자가 있는 부분을 다 탐색한것이므로 result를 1 증가 시켜줍니다. 

...

 

 

 

bfs

...

아직 방문하지 않은 graph[i][j]가 1인곳에서 bfs을 호출하고 graph[x][y] = 0 으로 방문처리 해줍니다.

 

상,하,좌,우 그리고 대각선에 대한 다음위치를 특정해주고 graph[nx][ny] == 1 이라면 queue에 nx, ny를 삽입하고 graph[i][j] = 0 으로 방문 처리합니다.

 

quque가 비게 된다면 글자가 있는 부분을 다 탐색한것이므로 result를 1 증가 시켜줍니다. 

...

 

 

 

 

 

파이썬 dfs

import sys
sys.setrecursionlimit(10000000)

def dfs(x,y):
    dx = [-1, 1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, -1, 1, -1, 1, -1, 1]
    graph[x][y] = 0

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]

        if (0 <= nx < m) and (0 <= ny < n) and graph[nx][ny] == 1:
            dfs(nx, ny)

m, n = map(int, input().split())

graph = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

result = 0;
for i in range(m):
    for j in range(n):
        if graph[i][j] == 1:
            dfs(i, j)
            result += 1

print(result)

 

 

 

 

 

파이썬 bfs

from collections import deque
from sys import stdin

def bfs(x, y):
    dx = [-1, 1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, -1, 1, -1, 1, -1, 1]
    
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0

    while queue:
        x, y = queue.popleft()

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < m) and (0 <= ny < n) and graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = 0            
    
    return

m, n = map(int, input().split())

graph = [list(map(int, stdin.readline().split())) for _ in range(m)]

result = 0;
for i in range(m):
    for j in range(n):
        if graph[i][j] == 1:
            bfs(i, j)
            result += 1
            
print(result)