슬라임문제_삼성DS준비

안녕하세요! 오늘은 삼성전자 S직군 대비 슬라임 문제를 가지고 왔습니다.

2018 하반기 SW 역량테스트 중 SDS 문제와 비슷한 유형인데, 내가 이동하는 위치와 나의 위치값 

차이를 비교하여 범위 내에 있을 경우 평균 값으로 대체하면서 재귀 진행을 하는 것입니다.

문제는 아래와 같습니다.

비슷한 유형 문제 중에서는 많이 꼬지를 않아서 어려운 문제는 아니었다.

그렇지만 처음 접했다면 분명 당황했을 문제이므로 반드시 정리하자

핵심은 현재 노드에서 상하좌우 노드 값을 먼저 체크하고 (노드 == 슬라임) 차이를 비교해서 범위 안에 들어가는지 먼저 체크합니다.

범위에 들어간다면, 해당 노드의 값을 합칩니다. (기존에 시작 노드는 값에 넣어놓은 다음에 시작할 예정)

이렇게 상하좌우 모든 값을 비교해서 차이가 범위 내의 값이라면 해당 값들을 모두 더하고 

카운트를 지속해서 증가시킵니다.

그렇게 평균을 구하고 평균 값으로 변화가 필요한 노드 값들을 바꿔줍니다.

여기서 필요한 함수는, 차이가 범위 안에 들어가는지 확인하는 함수 (나중에 평균으로 바꿀 때에도 필요함)

그리고 필요한 로직은 합과 카운트를 가지고 평균을 구하고 이를 변경해주는 과정이 필요합니다.

다음 과정을 선행한 뒤에 탐색을 진행합니다.

탐색은 단순히 이동입니다.

이동한 뒤 앞에 과정을 다시 진행하면 됩니다.

단!! 저는 탐색 이동 간에, 방문한 노드는 다시 방문하지 않기 위해서 boolean 값의 visited 배열을 

사용했는데, 혹시 이 부분 다른 방법이 있다면 댓글로 의견 남겨주시면 감사하겠습니다!

전체 코드는 아래와 같습니다.

---

---

[전체코드]

---

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class S기업_기출유사문제 {

private static int[][] slime;

private static int dx[] = { -1, 0, 1, 0 };

private static int dy[] = { 0, -1, 0, 1 };

private static int N;

private static boolean finish;

private static boolean visited[][];

private static boolean avgcheck[][];

private static int ret = 0; // 출력값(cnt);

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());

int X, Y;

N = Integer.parseInt(st.nextToken());

X = Integer.parseInt(st.nextToken());

Y = Integer.parseInt(st.nextToken());

slime = new int[N][N];

visited = new boolean[N][N];

for (int i = 0; i < N; i++) {

String[] node = br.readLine().split(" ");

for (int j = 0; j < N; j++) {

slime[i][j] = Integer.parseInt(node[j]);

}

}

dfs(0, 0, X, Y);

System.out.println(ret);

}

// 처음 노드 시작 --> 탐색, 상하좌우 체크

// 슬라임 무게가 X,Y 범위 내어야함

// px , py --> 이전 x, 이전 y

// check 함수를 지나서 true가 반환되면 평균값 계산 준비하기

private static boolean check(int node, int X, int Y) {

if (X <= node && Y >= node) {

return true;

}

return false;

}

private static void printAll() {

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

System.out.print(slime[i][j] + " ");

}

System.out.println("");

}

System.out.println("----------------------------");

}

private static void dfs(int px, int py, int X, int Y) {

// 기저 조건: 배열의 모든 요소가 범위 내에 있는 경우

avgcheck = new boolean[N][N];

visited[px][py] = true;

// printAll();

// refresh 제대로 되는지 확인 

int nx = 0;

int ny = 0;

int value = 0; // 총합 구하기 위한 변수

int count = 0; // 나눌 노드의 갯수

if (((px >= 0 && px < N) && (py >= 0 && py < N) && (ny < N && ny >= 0) && (nx >= 0 && nx < N))) {

if (check(slime[px][py], X, Y)) {

// 현재위치 (상하좌우 비교하지 않고 현재 무게 차이가 범위 내일 때)

avgcheck[px][py] = true;

value += slime[px][py];

count += 1;

}

}

// 현재 위치에서 좌노드 비교

nx = px - 1;

ny = py;

if ((px >= 0 && px < N) && (py >= 0 && py < N) && (ny < N && ny >= 0) && (nx >= 0 && nx < N)) {

if (check(Math.abs(slime[nx][ny] - slime[px][py]), X, Y)) {

avgcheck[nx][ny] = true;

value += slime[nx][ny];

count += 1;

}

}

nx = 0;

ny = 0;

// 우측 체크

nx = px + 1;

ny = py;

if ((px >= 0 && px < N) && (py >= 0 && py < N) && (ny < N && ny >= 0) && (nx >= 0 && nx < N)) {

if (check(Math.abs(slime[nx][ny] - slime[px][py]), X, Y)) {

avgcheck[nx][ny] = true;

value += slime[nx][ny];

count += 1;

}

}

// 상단 체크

nx = 0;

ny = 0;

nx = px;

ny = py - 1;

if ((px >= 0 && px < N) && (py >= 0 && py < N) && (ny < N && ny >= 0) && (nx >= 0 && nx < N)) {

if (check(Math.abs(slime[nx][ny] - slime[px][py]), X, Y)) {

avgcheck[nx][ny] = true;

value += slime[nx][ny];

count += 1;

}

}

// 하 체크

nx = 0;

ny = 0;

nx = px;

ny = py + 1;

if ((px >= 0 && px < N) && (py >= 0 && py < N) && (ny < N && ny >= 0) && (nx >= 0 && nx < N)) {

if (check(Math.abs(slime[nx][ny] - slime[px][py]), X, Y)) {

avgcheck[nx][ny] = true;

value += slime[nx][ny];

count += 1;

}

}

// Refresh 시작

nx = 0;

ny = 0;

int average = 1;

if (count != 0) {

average = (int) (value / count);

}

if (count > 1) {

ret += 1;

}

// 평균값 대체 (범위 벗어난 경우)

// 현재 위치부터 체크

// System.out.println(value + "/" + count + "/" + average);

if (((px >= 0 && px < N) && (py >= 0 && py < N))) {

if (avgcheck[px][py])

slime[px][py] = average;

}

nx = px - 1;

ny = py;

if ((ny < N && ny >= 0) && (nx >= 0 && nx < N)) {

if (avgcheck[nx][ny])

slime[nx][ny] = average;

}

nx = 0;

ny = 0;

nx = px + 1;

ny = py;

if ((ny < N && ny >= 0) && (nx >= 0 && nx < N)) {

if (avgcheck[nx][ny])

slime[nx][ny] = average;

}

nx = 0;

ny = 0;

nx = px;

ny = py - 1;

if ((ny < N && ny >= 0) && (nx >= 0 && nx < N)) {

if (avgcheck[nx][ny])

slime[nx][ny] = average;

}

nx = 0;

ny = 0;

nx = px;

ny = py + 1;

if ((ny < N && ny >= 0) && (nx >= 0 && nx < N)) {

if (avgcheck[nx][ny])

slime[nx][ny] = average;

}

// Refresh 완료

// 현재 위치에서 범위에 맞추기 위해서 dfs를 다시 돌릴 것인지

// 아니면 범위에 다 들어왔으므로 한 칸 이동해서 dfs를 돌릴지 체크

nx = 0;

ny = 0;

// 앞서 dfs를 안했다면 한 칸 이동해서 시작해봅시다!

for (int i = 0; i < 4; i++) {

nx = px + dx[i];

ny = py + dy[i];

if ((nx >= 0 && nx < N) && (ny >= 0 && ny < N))

if (check(Math.abs(slime[nx][ny] - slime[px][py]), X, Y)) {

return;

} else {

if (!visited[nx][ny])

dfs(nx, ny, X, Y);

}

}

}

}

---