#3184 : 양

풀이방법

사용된 것:

깊이우선탐색(DFS)

 

2022.05.25

그래프 탐색을 통해 각 영역에 속한 칸들을 탐색하고 양과 늑대의 마릿수를 세는 문제이다.

나는 깊이우선탐색을 사용하였다.

 

알고리즘은 다음과 같다.

 

마당의 특정 한 칸을 시작으로 깊이우선탐색을 하면, 그 칸과 같은 영역에 속하는 모든 칸을 한 번씩 방문할 수 있다. 이 과정에서 그 영역의 양과 늑대의 마릿수를 세어주면 된다.

이러한 과정을 마당의 모든 칸에 대하여 수행하면 문제가 해결된다.

 

 

다음은 코드 설명이다.

 

사용된 전역변수는 다음과 같다.

	static int r, c;	//마당의 크기(r은 행, c는 열 개수)
	static char[][] map;	//마당 지도
	static boolean[][] visited;	//방문여부 판별
	static int s, w;	//한 영역 안의 양(s)과 늑대(w)
	//아래는 상하좌우 좌표 계산에 쓰일 배열
	static int[] rchange = {-1, 1, 0, 0};
	static int[] cchange = {0, 0, -1, 1};

깊이우선탐색을 위한 함수가 재귀적으로 정의되기 때문에,

깊이우선탐색의 각 단계마다 계속해서 필요하되 그 값이 변동하지 않는 변수들은 모두 전역변수로 선언하였다.

 

 

 

깊이우선탐색 함수 dfs(int row, int col)은 일반적인 깊이우선탐색 함수에다가 양과 늑대를 세는 로직만 추가해준 형태이다. 그 내용은 다음과 같다.

 

이번에 탐색할 칸의 행과 열 좌표값 row, col이 주어지면

1. 이 칸이 마당 밖인지 확인한다. 마당 밖이라면 return한다.
2. 이 칸이 이미 방문한 칸인지 확인한다. 이미 방문한 칸이라면 return한다.
3. 이 칸이 울타리인지 확인한다. 울타리라면 return한다.
4. 위 세 단계에서 걸러지지 않았다면, 일단 이 칸을 방문했다고 표시해준 뒤 이 칸에 뭐가 있는지 확인한다. 양이 있다면 이번 영역의 양 마리수를 1 증가시키고, 늑대가 있다면 이번 영역의 늑대 마리수를 1 증가시킨다.
5. 이 칸의 상, 하, 좌, 우 좌표에 대하여 재귀호출한다.

 

 

이제 마당의 모든 칸에 대하여 다음과 같이 깊이우선탐색을 해주기만 하면 된다.

1. 한 영역 안의 양과 늑대 수를 저장하는 변수 s, w를 0으로 초기화시켜준다.
2. 해당 칸에 대하여 dfs를 실행한다.
3. dfs가 끝난 뒤 확정된 s와 w를 비교한다. s가 w보다 크다면 양이 더 많으므로 늑대를 몰아내는 영역이다. w의 값을 0으로 바꾼다. s가 w보다 크지 않다면 반대로 s의 값을 0으로 바꾼다.
4. s를 전체 양의 마릿수에 더하고, w를 전체 늑대의 마릿수에 더한다.

 

 

모든 칸에 대하여 위의 과정을 끝냈으면 전체 양의 마릿수와 전체 늑대의 마릿수를 화면에 출력한다.

 

코드

Java(2022.05.25)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	
	static int r, c;	//마당의 크기
	static char[][] map;	//마당 지도
	static boolean[][] visited;	//방문여부 판별
	static int s, w;	//한 영역 안의 양(s)과 늑대(w)
	//아래는 상하좌우 좌표 계산에 쓰일 배열
	static int[] rchange = {-1, 1, 0, 0};
	static int[] cchange = {0, 0, -1, 1};
	
	
	//깊이우선탐색으로 영역의 양과 늑대 마릿수를 세는 함수
	static void dfs(int row, int col) {
		//해당 칸이 마당 밖이거나 이미 방문한 칸이거나 울타리이면 돌아가기
		if(row < 0 || row >= r || col < 0 || col >= c) return;
		if(visited[row][col]) return;
		if(map[row][col] == '#') return;
		
		//아래는 이외의 경우
		
		//일단 방문했다고 표시
		visited[row][col] = true;
		
		//해당 칸에 뭐가 있는지 확인
		if(map[row][col] == 'v') w++;	//늑대가 있다면 이 영역의 늑대 마릿수 1 증가
		else if(map[row][col] == 'o') s++;	//양이 있다면 이 영역의 양 마릿수 1 증가
		
		//상하좌우에 대하여 재귀
		for(int i = 0; i<4; i++) dfs(row + rchange[i], col + cchange[i]);
		
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		map = new char[r][c];
		visited = new boolean[r][c];
		
		//마당 정보 읽어오기
		for(int i = 0; i<r; i++) {
			String input = br.readLine();
			for(int j = 0; j<c; j++) {
				map[i][j] = input.charAt(j);
			}
		}
		
		//정답을 저장할 변수 선언 및 0으로 초기화
		int sheep = 0;	//날이 밝았을 때 전체 양의 수
		int wolves = 0;	//날이 밝았을 때 전체 늑대의 수
		
		//모든 칸에 대하여 깊이우선탐색
		for(int i = 0; i<r; i++) {
			for(int j = 0; j<c; j++) {
				s = 0;	//이 칸이 속한 영역의 양 마릿수
				w = 0;	//이 칸이 속한 영역의 늑대 마릿수
				dfs(i,j);
				//이 영역에 양이 더 많다면 늑대를 없애고 그렇지 않다면 양을 없애기
				if(s>w) w = 0;
				else s = 0;
				//결과값을 정답에 반영
				sheep += s;
				wolves += w;
			}
		}
		
		//정답 출력
		System.out.print(sheep + " " + wolves);

	}

}