Search
Duplicate
📗

주차
문제번호
3184
언어
C++
티어
실버
유형
그래프
DFS
BFS
nj_Blog
nj_상태
이해도
100%
풀이
사람
이해도 2
13 more properties

문제접근

문자열 입력이기 때문에 vector<string>을 통해서 각 줄을 string으로 입력 받음
울타리가 아닌 부분을 dfs의 시작점으로 시작
방문한 곳은 울타리를 쳐버려서 방문 체크
dfs 한번 돌았을때 양수와 늑대 수 비교하고 결과 저장

놓쳤던 부분

코드

3052 KB

0 ms

#include <iostream> #include <vector> #include <string> using namespace std; int r, c; int dx[4] = {0, 1, 0, -1}; int dy[4] = {-1, 0, 1, 0}; int tmpSheepCount = 0; int tmpWolfCount = 0; vector<string> map; void dfs(int currentRow, int currentCol) { if (map[currentRow][currentCol] == 'v') tmpWolfCount++; else if (map[currentRow][currentCol] == 'o') tmpSheepCount++; map[currentRow][currentCol] = '#'; for (int i = 0; i < 4; i++) { int nextRow = currentRow + dy[i]; int nextCol = currentCol + dx[i]; if (nextRow < 0 || nextRow >= r || nextCol < 0 || nextCol >= c) continue ; if (map[nextRow][nextCol] == '#') continue ; dfs(nextRow, nextCol); } } int main(void) { int sheepCount = 0; int wolfCount = 0; ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> r >> c; map.resize(r); for (int i = 0; i < r; i++) cin >> map[i]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (map[i][j] != '#') { tmpSheepCount = 0; tmpWolfCount = 0; dfs(i, j); if (tmpSheepCount > tmpWolfCount) sheepCount += tmpSheepCount; else wolfCount += tmpWolfCount; } } } cout << sheepCount << " " << wolfCount; return (0); }
C++
복사