[BOJ 3184] 양 (Java, 그래프 탐색)알고리즘/그래프 탐색2023. 6. 9. 21:48
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/3184
풀이
- 전형적인 격자형 그래프 문제
- 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.
- '.' (점)은 빈 필드를, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미
- 상하좌우로만 이동가능하며, 울타리는 이동 불가
- (조건) 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다
- 영역별로 늑대의 수와 양의 수를 비교하여 살아 남은 양과 늑대의 수를 출력
- 시간 복잡도 : O(N^2) , 최대 N = 250인 경우에 Integer로 처리가능
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int R, C, SHEEP, WOLF;
static int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static boolean[][] visit;
static String[] MAP;
static void input() 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());
visit = new boolean[R][C];
MAP = new String[R];
for(int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
MAP[i] = st.nextToken();
}
}
static void bfs(int i, int j) {
Queue<Integer> que = new LinkedList<>();
que.add(i);
que.add(j);
visit[i][j] = true;
int _wolf = 0, _sheep = 0;
while(!que.isEmpty()) {
int x = que.poll(), y = que.poll();
if(MAP[x].charAt(y) == 'v') _wolf += 1;
if(MAP[x].charAt(y) == 'o') _sheep += 1;
for(int k = 0; k < 4; k++) {
int nx = x + direction[k][0];
int ny = y + direction[k][1];
if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if(visit[nx][ny]) continue;
if(MAP[nx].charAt(ny) == '#') continue;
que.add(nx);
que.add(ny);
visit[nx][ny] = true;
}
}
if(_sheep == 0 && _wolf == 0) return;
if(_sheep > _wolf) SHEEP += _sheep;
else WOLF += _wolf;
}
static void pro() {
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
if(!visit[i][j] && MAP[i].charAt(j) != '#') {
bfs(i, j);
}
}
}
sb.append(SHEEP).append(" ").append(WOLF);
System.out.println(sb);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
DFS로 풀 경우
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int R, C, SHEEP, WOLF, _S, _W;
static int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static boolean[][] visit;
static String[] MAP;
static void input() 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());
visit = new boolean[R][C];
MAP = new String[R];
for(int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
MAP[i] = st.nextToken();
}
}
static void dfs(int x, int y) {
visit[x][y] = true;
if(MAP[x].charAt(y) == 'v') _W += 1;
if(MAP[x].charAt(y) == 'o') _S += 1;
for(int i = 0; i < 4; i++) {
int nx = x + direction[i][0];
int ny = y + direction[i][1];
if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if(visit[nx][ny]) continue;
if(MAP[nx].charAt(ny) == '#') continue;
dfs(nx, ny);
}
}
static void pro() {
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
if(!visit[i][j] && MAP[i].charAt(j) != '#') {
_W = 0;
_S = 0;
dfs(i, j);
if(_S > _W) SHEEP += _S;
else WOLF += _W;
}
}
}
sb.append(SHEEP).append(" ").append(WOLF);
System.out.println(sb);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
반응형
'알고리즘 > 그래프 탐색' 카테고리의 다른 글
[BOJ 11403] 경로 찾기 (Java, 그래프 탐색) (0) | 2023.06.09 |
---|---|
[BOJ 2606] 바이러스 (Java, 그래프 탐색) (0) | 2023.06.09 |
[BOJ 2667] 단지번호붙이기 (Java, 그래프 탐색) (0) | 2023.06.09 |
[BOJ 11724] 연결 요소의 개수 (Java, 그래프 탐색) (0) | 2023.06.09 |
[BOJ 1012] 유기농 배추 (Java, 그래프 탐색) (0) | 2023.06.09 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!