양
문제 정보
- 사이트 : 백준 알고리즘 사이트
- 문제 번호 : 3184
- 문제 분류 : dfs
- 난이도 : silver 1
문제 풀이
내가 짠 코드
생각한 문제 조건
1. n,m으로 map 주어진다.
2. '.'은 빈필드, '#'은 울타리, 'o'은 양, 'v' 늑대를 의미한다.
3. 늦대는 수평, 수직으로만 이동가능하다.
4. '같은 영역' = 울타리를 넘지 않고 수평 수직으로 연결된 칸들
5. 양의 수 > 늑대 수 = 양 win 나머지 늑대 win
💭 생각 노트
- map을 탐색하다 양이나 늑대가 있으면 dfs 시작
- 탐색을 하면서 만나는 양과 늑대의 수를 저장
- 탐색이 끝났을 때 수를 비교해서 누가 살아남은 수를 저장
- 전체 방문 후 저장한 양과 늑대 수 출력
public class BJ_3184 {
static int n,m;
static String[][] map;
static boolean[][] visit;
static int[][] check = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int ocount, vcount = 0;
public static void dfs(int x, int y){
// 양과 늑대 수 check
if(map[x][y].equals("o"))
ocount++;
if(map[x][y].equals("v"))
vcount++;
// 이동 check
for (int i = 0; i < 4; i++) {
int dx = x + check[i][0];
int dy = y + check[i][1];
if(0 <= dx && dx < n && 0 <= dy && dy < m){
// 같은 영역이면 이동
if(!visit[dx][dy] && !map[dx][dy].equals("#")){
visit[dx][dy] = true;
dfs(dx, dy);
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
map = new String[n][m];
visit = new boolean[n][m];
int o = 0, v = 0;
for (int i = 0; i < n; i++) {
input = br.readLine().split("");
for (int j = 0; j < m; j++) {
map[i][j] = input[j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(!visit[i][j] && !map[i][j].equals(".") && !map[i][j].equals("#")){
visit[i][j] = true;
ocount = 0;
vcount = 0;
dfs(i, j);
// 탐색 후 양이 크면 양이 살아 남고 나머진 늑대가 살아남음
if(ocount > vcount)
o += ocount;
else
v += vcount;
}
}
}
System.out.println(o + " " + v);
br.close();
}
}