[백준/Baekjoon] 14716 현수막 C++/Python :: BFS & DFS

https://www.acmicpc.net/problem/14716

14716번: 현수막

---

1. Logic

문제에서 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 "인접하여 서로 연결"되어있다고 했기 때문에 그래프를 떠올릴 수 있다. 더해서 상, 하, 좌, 우, 대각선이기 때문에 8방향 BFS 또는 DFS로 풀이해줄 수 있다. 풀이 과정은

1. 입력받기

2. 1과 동시에 방문하지 않은 좌표 방문하기

3. bfs or dfs에서 8방향 확인해서 1, 미방문 좌표 들어가기

4. 함수 호출한 횟수 count

C++은 BFS로 파이썬은 연습중이라 BFS, DFS 두가지 방법 모두 풀이해봤다.

728x90

---

2. Code

C++

#include<bits/stdc++.h>

using namespace std;

int n, m;

int word[251][251];
bool vis[251][251];

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};

void bfs(int yy, int xx) {
    queue<pair<int, int>> q;
    
    q.push({yy, xx});
    vis[yy][xx] = true;
    
    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        
        q.pop();
        
        for(int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if(vis[ny][nx]) continue;
            if(!word[ny][nx]) continue;
            
            vis[ny][nx] = true;
            
            q.push({ny, nx});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> word[i][j];
        }
    }
    
    int cnt = 0;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(!word[i][j]) continue;
            if(vis[i][j]) continue;
            
            bfs(i, j);
            cnt++;
        }
    }
    
    cout << cnt;
}

Python - BFS

from collections import deque

d = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]

def bfs(yy, xx):
    q = deque()
    q.append((yy, xx))
    vis[yy][xx] = True
    
    while q:
        y, x = q.popleft()
        for ny, nx in d:
            nx = nx + x
            ny = ny + y
            if(nx < 0 or nx >= m or ny < 0 or ny >= n):
                continue
            if(word[ny][nx] == 0):
                continue
            if(vis[ny][nx]):
                continue
            
            q.append((ny, nx))
            vis[ny][nx] = True

n, m = map(int, input().split())
word = [list(map(int, input().split())) for _ in range(n)]
vis = [[False]*m for _ in range(n)]

cnt = 0

for i in range(n):
    for j in range(m):
        if word[i][j] == 0 or vis[i][j]:
            continue
        bfs(i, j)
        cnt += 1

print(cnt)

Python - DFS

import sys
sys.setrecursionlimit(100000)

def dfs(y, x):
    word[y][x] = 0
    
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if(nx < 0 or nx >= m or ny < 0 or ny >= n):
            continue
        if(not word[ny][nx]):
            continue
        dfs(ny, nx)
    return True
    
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

n, m = map(int, input().split())
word = [list(map(int, input().split())) for _ in range(n)]
vis = [[False]*m for _ in range(n)]
    
cnt = 0
    
for i in range(n):
    for j in range(m):
        if word[i][j]:
            dfs(i, j)
            cnt += 1
print(cnt)

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐