[BOJ]3184番羊(Java)
3795 ワード
質問する (Silver 2)
3184号:楊
に答える
1.ヒツジやオオカミがいるエリアをチェック(BFS)
2.回転パターン羊と狼の位置を保存
3.ナビゲート後、羊とオオカミのリストの大きさを比較して地図にマッピングする
コード#コード#
import java.util.*;
import java.io.*;
public class Main {
static int[] di = {-1,0,1,0};
static int[] dj = {0,-1,0,1};
static int R,C;
static char[][] map;
static boolean[][] visited ;
static List<int[]> sheep, inSheep;
static List<int[]> wolf, inWolf;
public static void main(String[] args) throws Exception{
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];
sheep = new ArrayList<>(); // 영역 내 양의 위치 저장
wolf = new ArrayList<>(); // 영역 내 늑대 위치 저장
for(int i =0 ; i < R ; i++){
String str = br.readLine();
for(int j =0 ; j < C ; j++){
map[i][j] = str.charAt(j);
}
}
for(int i =0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
if(map[i][j] == 'v' || map[i][j] == 'o'){ // 늑대와 양을 만난다면
wolf = new ArrayList<>();
sheep = new ArrayList<>();
attack(i, j); // 영역 검사
if(wolf.size() < sheep.size()){ // 양의 수가 더 많을 때
for(int[] w : wolf){
map[w[0]][w[1]] = '.'; // 늑대 위치 값 변경
}
}else{
for(int[] s : sheep){ // 늑대 수가 더 많을 때
map[s[0]][s[1]] = '.'; // 양의 위치 값 변경
}
}
}
}
}
int wolfCnt = 0;
int sheepCnt = 0;
for(int i =0 ; i < R ; i++){
for(int j =0 ; j < C ;j++){
if(map[i][j] == 'v') wolfCnt ++;
else if(map[i][j] == 'o') sheepCnt++;
}
}
System.out.println(sheepCnt+" "+wolfCnt);
}
/* 영역 검사를 위한 BFS */
private static void attack(int i, int j) {
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{i, j});
visited[i][j] = true;
while(!q.isEmpty()){
int[] cur = q.poll();
if(map[cur[0]][cur[1]] == 'v'){
wolf.add(new int[]{cur[0], cur[1]});
}
else if(map[cur[0]][cur[1]] == 'o') {
sheep.add(new int[]{cur[0], cur[1]});
}
for(int d = 0 ; d < 4 ; d++){
int ni = cur[0] + di[d];
int nj = cur[1] + dj[d];
if(0<=ni&&ni<R && 0<=nj&&nj<C){
if(!visited[ni][nj] && map[ni][nj] != '#'){
q.offer(new int[]{ni, nj});
visited[ni][nj] = true;
}
}
}
}
}
}
Reference
この問題について([BOJ]3184番羊(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ-3184번-양-Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol