[BOJ] 양

문제

미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.

다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기게 된다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

입력

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

 

풀이

3184

맞았습니다!!

3308

0

C++14 / 수정

1791

38초 전

 

1. 완전 탐색 

 

1-1. 예시를 보면 한 영역은 울타리로 전부 막혀있다. 다른 영역으로 이동할 수 없다. 즉, 한 영역 안에 있는 늑대와 양의 수만 세면 된다. 

 

2. bfs는 울타리안의 영역을 돌면서 양과 늑대의 수를 반환한다.

map의 값이 'o'이면 pair의 second의 값을 1만큼 증가하고, 'v'이면 pair의 first의 값을 1만큼 증가시킨다. 

 

3. 영역을 전부 돌고나서 늑대의 수가 양의 수보다 크거나 같다면 결과 pair에 늑대의 수만 더하고, 양의 수가 더 크다면 양의 수만 더해준다.

---

 

 

#include <iostream> #include <vector> #include <queue> using namespace std; int r, c; char map[251][251]; typedef pair<int, int> pp; vector<pp> wolf, sheep; bool visited[251][251]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; pp bfs(int x, int y) { queue<pp> q; q.push(pp(x, y)); pp res; if (map[x][y] == 'v') { res.first += 1; } else if (map[x][y] == 'o') res.second += 1; visited[x][y] = true; while (!q.empty()) { int size = q.size(); while (size--) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= r || ny < 0 || ny >= c || visited[nx][ny] || map[nx][ny] == '#') continue; if (map[nx][ny] == 'v') { res.first += 1; } else if (map[nx][ny] == 'o') res.second += 1; visited[nx][ny] = true; q.push(pp(nx, ny)); } } } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> r >> c; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cin >> map[i][j]; if (map[i][j] == 'v') { wolf.push_back(pp(i, j)); } else if (map[i][j] == 'o') { sheep.push_back(pp(i, j)); } } } pp ans; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (!visited[i][j] && map[i][j] != '#') { pp res = bfs(i, j); if (res.first >= res.second) ans.first += res.first; else ans.second += res.second; } } } cout << ans.second << " " << ans.first << '\n'; return 0; }