https://www.acmicpc.net/problem/3184
문제 설명
o:양/v: 늑대 /#: 울타리 /.: 빈 필드
주어진 영역에서양 > 늑대일 시, 늑대는 영역에서 쫓겨나게 되며, 그렇지 않으면 (양 <= 늑대) 모든 양이 잡아먹힌다.
단, 영역은#울타리로 둘러싸여있으면 다른 영역으로 간주된다.
즉, 이 맵엔 영역이 총 2개인 것이다.
이러한 조건일 때, 맵안의 양과 늑대의 수를 구해야 한다.
전체 코드
package backJoon_3184_sheep;
import java.util.*;
public class Practice {
static Scanner sc = new Scanner(System.in);
static char map[][];
static boolean visited[][];
static int y, x;
static int divNumberOfSheep, divNumberOfWolf = 0;
public static void main(String[] args) {
input();
int numberOfSheep = 0;
int numberOfWolf = 0;
for(int i = 0; i < y; i++) {
for(int j = 0; j < x; j++) {
if(visited[i][j] == false && map[i][j] != '#') {
visited[i][j] = true;
if(map[i][j] == 'v') {
divNumberOfWolf++;
}else if(map[i][j] == 'o') {
divNumberOfSheep++;
}
dfs(i, j);
if(divNumberOfSheep > divNumberOfWolf) {
divNumberOfWolf = 0;
}else {
divNumberOfSheep = 0;
}
numberOfSheep += divNumberOfSheep;
numberOfWolf += divNumberOfWolf;
divNumberOfSheep = 0;
divNumberOfWolf = 0;
}
}
}
System.out.println("양: "+numberOfSheep+" 늑대: "+numberOfWolf);
}
private static void dfs(int i, int j) {
int[] dy = {1, -1, 0, 0};
int[] dx = {0, 0, 1, -1};
int ny, nx;
for(int d = 0; d < 4; d++) {
ny = i + dy[d];
nx = j + dx[d];
if(isArrange(ny,nx) && map[ny][nx] != '#' && visited[ny][nx] == false) {
visited[ny][nx] = true;
if(map[ny][nx] == 'v') {
divNumberOfWolf++;
}else if(map[ny][nx] == 'o') {
divNumberOfSheep++;
}
dfs(ny,nx);
}
}
}
private static boolean isArrange(int ny, int nx) {
return ny >= 0 && nx >= 0 && ny < y && nx < x;
}
private static void input() {
y = sc.nextInt();
x = sc.nextInt();
map = new char[y][x];
visited = new boolean[y][x];
String temp;
for(int i = 0; i < y; i++) {
temp = sc.next();
for(int j = 0; j < x; j++) {
map[i][j] = temp.charAt(j);
}
}
/*
for(int i = 0; i < y; i++) {
for(int j = 0; j < x; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}*/
}
}문제 풀이
for(int i = 0; i < y; i++) {
for(int j = 0; j < x; j++) {
if(visited[i][j] == false && map[i][j] != '#') {
visited[i][j] = true;
if(map[i][j] == 'v') {
divNumberOfWolf++;
}else if(map[i][j] == 'o') {
divNumberOfSheep++;
}
dfs(i, j);
...일단 for문을 돌며, 아직 방문하지 않았으며 울타리가 아닌 영역을 탐색한다.
if문 조건을 만족하면visited로 방문체크를 하고, 해당 영역이 늑대인지 양인지 확인해 count 한다.
그 후 재귀함수를 호출한다.
for(int d = 0; d < 4; d++) {
ny = i + dy[d];
nx = j + dx[d];
if(isArrange(ny,nx) && map[ny][nx] != '#' && visited[ny][nx] == false) {
visited[ny][nx] = true;
if(map[ny][nx] == 'v') {
divNumberOfWolf++;
}else if(map[ny][nx] == 'o') {
divNumberOfSheep++;
}
dfs(ny,nx);
}
}재귀함수
dfs()에서 네 방향으로 영역을 탐색하며, 늑대일 경우divNumberOfWolf를 count 해주고, 양일 경우엔divNumberOfSheep을 count 하는 과정을 반복한다.
만약 사방이#으로 막혀있다면 더 이상 탐색 불가이므로 재귀에서 빠져나와 맨 처음dfs()를 호출했던main()메소드로 돌아가게 된다.
if(divNumberOfSheep > divNumberOfWolf) {
divNumberOfWolf = 0;
}else {
divNumberOfSheep = 0;
}
numberOfSheep += divNumberOfSheep;
numberOfWolf += divNumberOfWolf;
divNumberOfSheep = 0;
divNumberOfWolf = 0;앞서 탐색했던 부분이 하나의 영역이므로 그 영역 안에서 count 했던 양과 늑대의 수 (
divNumberOfSheepdivNumberOfWolf)를 비교한다.
양이 더 많다면 늑대는 해당 영역에서 모두 쫓겨나게 되므로divNumberOfWolf는0이 된다.
그렇지 않다면divNumberOfSheep이0이 된다.
그 후에 양과 늑대의 총 수 (numberOfSheepnumberOfWolf)에 더해준다.
굳이 이렇게div가 붙은 변수와 그렇지 않은 변수로 하는 이유는, 영역마다 양과 늑대의 수가 달라서 어느 영역에서 어느 동물이0이 되는지 알 수 없기 때문이다.
총 수에 더해준 후div변수는 다음영역 탐색을 위해 반드시 초기화해야 한다.
이렇게 해서 문제의 테스트케이스는 모두 통과를 했다.
그런데 제출하면 자꾸 메모리초과 문제가 발생하는 것이었다....
DFS 문제에서 메모리초과라 함은 대부분이 무한호출이 문제라는데...
나는 무한호출 될만한 부분이 아무리 봐도 없었다ㅠ
최대 범위인250 250도 입력해봤으나 답은 잘만 나오는데...
인터넷 검색을 해보니 사람들은 이 문제를 DFS가 아닌 BFS로 풀고 있었다.
설마 이게 문제일까 싶어서 BFS로도 풀어봤는데 그래도 메모리초과가 발생했다.
▼ BFS 버전
public class Practice {
static Scanner sc = new Scanner(System.in);
static String map[][];
static boolean visited[][];
static int y, x;
static int divNumberOfSheep, divNumberOfWolf = 0;
static Queue<Coordinate> q = new LinkedList<>();
public static class Coordinate{
int Y;
int X;
public Coordinate(int Y, int X) {
this.Y = Y;
this.X = X;
}
}
public static void main(String[] args) {
readInput();
int numberOfSheep = 0;
int numberOfWolf = 0;
for(int i = 0; i < y; i++) {
for(int j = 0; j < x; j++) {
if(visited[i][j] == false && !"#".equals(map[i][j])) {
visited[i][j] = true;
if("v".equals(map[i][j])) {
divNumberOfWolf++;
}else if("o".equals(map[i][j])) {
divNumberOfSheep++;
}
q.offer(new Coordinate(i, j));
bfs(q);
if(divNumberOfSheep > divNumberOfWolf) {
divNumberOfWolf = 0;
}else {
divNumberOfSheep = 0;
}
numberOfSheep += divNumberOfSheep;
numberOfWolf += divNumberOfWolf;
divNumberOfSheep = 0;
divNumberOfWolf = 0;
}
}
}
System.out.println("양: "+numberOfSheep+" 늑대: "+numberOfWolf);
}
private static void bfs(Queue<Coordinate> q) {
int[] dy = {1, -1, 0, 0};
int[] dx = {0, 0, 1, -1};
int ny, nx;
Coordinate coord;
while(!q.isEmpty()) {
coord = q.poll();
int i = coord.Y;
int j = coord.X;
for(int d = 0; d < 4; d++) {
ny = i + dy[d];
nx = j + dx[d];
if(isArrange(ny,nx) && !"#".equals(map[ny][nx]) && visited[ny][nx] == false) {
visited[ny][nx] = true;
if("v".equals(map[ny][nx])) {
divNumberOfWolf++;
}else if("o".equals(map[ny][nx])) {
divNumberOfSheep++;
}
//dfs(ny,nx);
q.offer(new Coordinate(ny, nx));
}
}
}
}
private static boolean isArrange(int ny, int nx) {
return ny >= 0 && nx >= 0 && ny < y && nx < x;
}
private static void readInput() {
y = sc.nextInt();
x = sc.nextInt();
map = new String[y][x];
visited = new boolean[y][x];
String temp;
for(int i = 0; i < y; i++) {
temp = sc.next();
for(int j = 0; j < x; j++) {
map[i] = temp.split("");
}
}
/*
for(int i = 0; i < y; i++) {
for(int j = 0; j < x; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}*/
}
}그냥 포기할까도 생각했지만 도대체 어느 부분에서 메모리초과가 발생하는걸까 너무 궁금해서 도저히 버려지지가 않았다ㅠ
그러다가 아주 어이없는 부분에서 메모리 초과가 발생했다는 사실을 알게 되었다...
static String map[][];바로
map[][]객체가 문제였다...
String타입이었기 때문에 메모리 초과가 발생한 것이었다...ㅠㅠㅠ
이map[][]의 타입을char타입으로 바꿔주니 바로 통과해버렸다..ㅠㅠㅠㅠㅠㅠ
어이도 없었지만 앞으로는 굳이char도 있는데String으로 풀지 말아야겠다는 생각이 들었다!ㅠ
Git gist 주소
