[백준] S2 3184 양 (java)

www.acmicpc.net/problem/3184

3184번: 양

 

풀이

 

1) 맵, 방문체크, 총 양, 총 늑대를 static으로 선언

2) 2중 포문으로 맵을 돌면서 방문체크가 안되어있고 #인 경우 bfs탐색

2-1) bfs를 돌때마다 한 울타리 내에 양의 수와 늑대의 수를 기억함

2-2) 양의 수가 크면 총 양에 더함, 작거나 같으면 총 늑대에 더함

3) 총 양과 총 늑대의 수를 출력

 

주의사항

 

1) 없다. 함정이 없는 깔끔한 문제.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_S2_3184_양 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int R,C,totalWolf,totalSheep;
	static boolean isVisited[][];
	static char map[][];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		R = Integer.parseInt(tokens.nextToken());
		C = Integer.parseInt(tokens.nextToken());
		map = new char [R][C];
		isVisited = new boolean[R][C];
		for(int r=0; r<R; r++) {
			String line = input.readLine();
			for(int c=0; c<C; c++) {
				map[r][c] = line.charAt(c);
			}	
		}
		for(int r=0; r<R; r++) {
			for(int c=0; c<C; c++) {
				if(!isVisited[r][c] && map[r][c] != '#') {
					bfs(r,c);
				}
			}	
		}
		System.out.println(totalSheep +" "+ totalWolf);
	}

	private static void bfs(int r, int c) {
		Queue<Node> queue = new LinkedList<>();
		queue.add(new Node(r, c));
		isVisited[r][c] = true;
		int sheep = 0, wolf = 0;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			if(map[front.r][front.c] == 'o') {
				sheep++;
			}else if(map[front.r][front.c] == 'v') {
				wolf++;
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				
				if(isIn(nr, nc) && !isVisited[nr][nc] && map[nr][nc] != '#') {
					queue.offer(new Node(nr, nc));
					isVisited[nr][nc] = true;
				}
			}
		}
		if(sheep > wolf) {
			totalSheep += sheep;
		}else {
			totalWolf += wolf;
		}
	}
	
	static int dr[] = {0,0,-1,1};
	static int dc[] = {-1,1,0,0};
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<R && c<C);
	}
	static class Node{
		int r;
		int c;
		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + "]";
		}
	}

	static String src =
			"6 6\r\n" + 
			"...#..\r\n" + 
			".##v#.\r\n" + 
			"#v.#.#\r\n" + 
			"#.o#.#\r\n" + 
			".###.#\r\n" + 
			"...###";
}

 

 

후기

 

보자마자 후다닥 풀 수 있었을 것 같지만 혹시몰라서 노트에 먼저 설계를 한 뒤에 시작했다.

다행히 막힘 없이 풀어서 한번에 통과했다.