🔍양
<문제>
미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.
마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.
한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.
다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.
맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.
아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.
💡
import java.util.*;
import java.io.*;
class Main {
static int R, C;
static char[][] field;
static boolean visit[][]; // 방문했는지 확인하기 위한 boolean배열
static int dx[] = {-1,1,0,0}; // 좌우로 이동.
static int dy[] = {0,0,-1,1}; // 상하로 이동.
static int countSheep = 0; // 필드안 양의 수.
static int countWolf = 0; // 필드안 늑대의 수.
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력값
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 출력값
int resultSheep = 0; // 살아남은 양의 수.
int resultWolf = 0; // 살아남은 늑대의 수.
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
visit = new boolean[R][C]; // 받아온 입력값으로 배열 크기 지정.
field = new char[R][C]; // 받아온 입력값으로 field 크기 지정.
for(int i=0; i<R; i++) { // 필드에 입력값 채워주기.
field[i] = br.readLine().toCharArray();
}
for(int k=0; k<R; k++) {
for(int l=0; l<C; l++) {
if(field[k][l] == '#' || k==0 || k==R-1 || l==0 || l == C-1){
visit[k][l] = true; // 울타리, 필드밖으로 통하는 영역은 방문표시하기.
}
}
}
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) { // 필드의 (0, 0)부터 탐색하면서
if(!visit[i][j]) { // 방문안했으면
if(field[i][j]=='o'){
countSheep = 1; // o면 양+1
}else if(field[i][j]=='v'){
countWolf = 1; // v면 늑대+1
}
dfs(i,j); // 그 공간의 양과 늑대 수 세기 위해 상하좌우 탐색.
if(countWolf>0 || countSheep>0){ // 울타리 안 공간에 양 또는 늑대가 존재하고,
if(countSheep>countWolf){ // 양이 더 많으면
resultSheep = resultSheep + countSheep; // 살아남은 양에 더해줌.
}else{ // 늑대가 더 많거나 같으면
resultWolf = resultWolf + countWolf; // 살아남은 늑대에 더해줌
}
countSheep=0; // 양의 수 초기화.
countWolf=0; // 늑대의 수 초기화.
}
}
}
}
bw.write(String.valueOf(resultSheep+" "+resultWolf)); // 양과 늑대 마리수 출력
br.close();
bw.flush();
bw.close();
}
public static void dfs(int x, int y) {
visit[x][y] = true;
for(int i=0; i<4; i++) { // 그 필드의 상하좌우확인.
int nx = x + dx[i];
int ny = y + dy[i];
if(!visit[nx][ny]) { // 방문안했으면
if(field[nx][ny]=='o'){
countSheep++; // o면 양+1
}else if(field[nx][ny]=='v'){
countWolf++; // v면 늑대+1
}
dfs(nx,ny); // 그 곳의 상하좌우확인하기
}
}
}
}
Cherish the moment :)