8주차 스터디 그래프 이론 - 백준 3184번 양

www.acmicpc.net/problem/3184

3184번: 양

 

IDEA

고냥 깜찍한 BFS/DFS문제다. DFS보단 BFS가 편해 BFS로 풀었다. 

'#'이라는 울타리로 막혀있는 공간 안에서 양과 늑대의 개수를 세어, 더 많은 동물의 개수가 살아남아 최종적으로 아침까지 살아있는 양과 늑대의 수를 구하는 문제다. 

 

1. #이 아니면 BFS문 돌림 

2. 큐에서 꺼낸 좌표에 O가 존재하면 양을 , V가 존재하면 늑대의 수를 하나 세준다. 

3. 상하좌우에 대해서 마당을 넘어가지 않으며 , 방문하지 않았고, "#"이 아니라면 큐에 넣어준다.

4. 큐가 비어 반복문이 끝나면 who_lives라는 함수로 한 구역 내에 양과 늑대의 수를 넘겨준다.

5. who_lives라는 함수에서는 둘의 대소관계를 비교하여 양이 더 많다면 양의 수를 , 양이 더 적거나 같다면 늑대의 수를 더해준다. 

 

c++로 코드를 작성한 후, 파이썬으로 작성했는데

최성철 교수님이 말씀해주신대로 함수를 최소한의 의미단위?라고 해야되나

최대한 하나의 함수에는 유사한 기능들만 모여있을 수 있도록 짜려고 노력해봤다. 

 

CODE - C++

#include <iostream>
#include <vector>
#include<algorithm>
#include<queue>
#include<string.h>

using namespace std;

vector<string>map;
queue<pair<int, int>>q;
bool visited[255][255] = { false };
int n, m ,total_sheep = 0, total_wolf = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

bool check(int x, int y) {
    if (0 <= x && x < n && 0 <= y && y < m && !visited[x][y] && map[x][y] !='#')  return true;//범위 내에 있으면서 방문 x 
    return false;
}

void bfs(int startx, int starty) {
    int wolf = 0, sheep = 0;
    q.push({ startx , starty });
    visited[startx][starty] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (map[x][y] == 'o') sheep++;
        if (map[x][y] == 'v') wolf++;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (check(nx, ny)) {
                q.push({ nx,ny });
                visited[nx][ny] = true;
            }
        }
    }

    if (sheep != 0 || wolf != 0) {
        if (sheep > wolf) total_sheep += sheep;
        else total_wolf += wolf;
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
	cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        map.push_back(str);
    }
    int live_sheep = 0, live_wolf = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j]  && map[i][j] != '#'){
                bfs(i, j);
            }
        }
    }
    printf("%d %d", total_sheep, total_wolf);
}

CODE - Python

from collections import deque

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

madang = [list(input().strip()) for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]
how_many_live = [0,0] #sheep, wolf

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

def check(x,y) :
  return 0<=x<n and 0 <=y<m and not visited[x][y] and madang[x][y] != "#"

def who_lives(s , w) :
  if s > w : how_many_live[0] += s
  else : how_many_live[1] += w

def bfs(sx,sy):
  q = deque([[sx,sy]])
  visited[sx][sy] = True
  sheep = 0
  wolf = 0

  while q : 
    x , y = q.popleft()
    if (madang[x][y] == "o"): sheep += 1
    if (madang[x][y] == "v") : wolf += 1

    for i in range(4) :
      nx = x + dx[i]
      ny = y + dy[i]
      if (check(nx,ny)):
        q.append([nx,ny])
        visited[nx][ny] = True
        
  who_lives(sheep , wolf)

for i in range(n):
  for j in range(m) :
    if (check(i,j)): bfs(i,j)

print(how_many_live[0])
print(how_many_live[1])