SW_EXPERT 1861 정사각형 방

정사각형 방 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE

문제 무단 배포를 막기 위해서 링크로 포스팅 하였습니다.

이번 문제는 전형적인 탐색입니다.  동서남북으로 이동할 수 있으며, 본인보다 값 1이 더 큰 방만 이동할 수 있다.

이동할 경우 가장 방을 많이 방문하는 횟수와 그 출발 방을 구하시오.

단! 횟수가 같을 경우 방 번호가 더 작은 값으로 출력해야 합니다.

[전체 코드]

---

import java.io.BufferedReader;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Scanner;

public class 정사각형_방 {

private static int board[][];

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

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

private static int N = 0;

private static int cmp_cnt = 0;

private static int start_node = 0;

public static void main(String[] args) throws NumberFormatException, IOException {

// TODO Auto-generated method stub

//System.setIn(new FileInputStream("res/input.txt"));

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int testCase = Integer.parseInt(br.readLine());

int inx = 0;

while (testCase-- > 0) {

N = Integer.parseInt(br.readLine());

board = new int[N][N];

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

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

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

board[i][j] = Integer.parseInt(line[j]);

}

}

start_node = board[0][0];

cmp_cnt = 0;

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

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

checkTheLongestRoute(i, j, 1, board[i][j]);

}

}

System.out.println("#" + (++inx) + " " + start_node + " " + cmp_cnt);

}

}

// 출발 노드에 대해서 이동 가능한 횟수 체크하는 함수

private static void checkTheLongestRoute(int x, int y, int count, int a) {

// N이 2라면 (0,0) , (0,1) , (1,0) , (1,1) 위치에서 출발 할 것

// 그리고 여기서 상하좌우로 이동할건데 조건으로 그 이동할 곳이 1이 더 커여함

// 범위도 N보다 작거나 같고 0보다 커야함

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

int nx = x + dx[i]; // (0,0)에서 처음 한 칸 이동

int ny = y + dy[i];

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

if (board[nx][ny] - board[x][y] == 1) {

// 이동할 노드에 대해서 크기 차이가 1일 때 (이동할 노드가 1이 더 크다는 것)

checkTheLongestRoute(nx, ny, ++count, a);

}

}

}

if(cmp_cnt == count) {

if (start_node > a) {

start_node = a;

}

}

if (cmp_cnt < count) {

cmp_cnt = count;

start_node = a;

}

}

}

---

조건 그대로 적어주시면 됩니다. 

단, 필자는 카운트와 값을 줄 때 처음에 인자로 주지 않고 전역변수로 두어 계속해서 초기화 시키면서 비교했습니다.

그러다보니, 가리키는 값이 다른데도 불구하고, 그걸로 비교하는 경우가 발생했습니다.

가령, 4 -> 5 -> 6 이렇게 될 때, 6에서 다시 돌아오면서 가장 작은 방은 4로 체크해서 비교해야 하는데, 

5랑 비교하고 있는 문제가 발생했습니다.

따라서 번거로움을 피하고자 인자에 방의 번호와 카운트 모두 추가하였고 다음과 같이 재귀 호출을 하면 됩니다.

간단하게 로직을 설명하면, 2x2배열일 때, 4칸 모두 첫 스타트 점으로해서 각각 탐색을 시작합니다.

그러면서 별도의 기저 조건을 주지 않는 것도, 조건에서 이동할 방이 현재 방보다 1만큼 더 커야한다고 하였으므로 

해당 조건일 때만 재귀 호출을 하면 됩니다.

또한 이동할 때 이동한 좌표로 이동해야하며, 카운트도 하나 증가 시켜야 합니다.

한 노드(방)에 대해서 탐색이 끝나면 카운트 된 것이 전역으로 정의된 카운트와 대소 비교를 합니다.

대소 비교를 통해서 전역 변수로 선언한 카운트에 현재 카운팅된 횟수를 대입합니다.

그리고 방의 번호를 값에 넣고 다시 진행합니다.

이는, 조건에 나온대로만 그대로 진행하면 되는 부분이라 크게 어렵지 않을 것입니다.

추가로 다음 테스트케이스에선 전역으로 카운트 된 값은 초기화 해줘야 합니다.

감사합니다.