SW 역량테스트 - [모의 SW 역량테스트] 등산로 조성 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

해답 코드 : 

 

// c++

#include <iostream>
#include <algorithm>
using namespace std;

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

int t, n, k, res;
int input[9][9];
bool visit[9][9];


void dfs(int x, int y, int cnt, int flag) {
	visit[x][y] = true;
	if (res < cnt) res = cnt;

	for (int i = 0; i < 4; i++) {
		int ax = x + dx[i];
		int ay = y + dy[i];

		//방문했거나 범위 벗어나면 continue
		if (ax == 0 || ay == 0 || ax == n + 1 || ay == n + 1 || visit[ax][ay]) continue;

		//내리막길인 경우
		if (input[x][y] > input[ax][ay]) {
			dfs(ax, ay, cnt + 1, flag);
		}
		//내리막길이 아닌 경우
		else {
			if (input[x][y] > input[ax][ay] - k && flag) {

				int temp = input[ax][ay];

				input[ax][ay] = input[x][y] - 1;
				dfs(ax, ay, cnt + 1, 0);
				input[ax][ay] = temp; // 원상 복귀
			}
		}
	}
	visit[x][y] = false;
}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> t;

	for (int tc = 1; tc <= t; tc++) {

		cin >> n >> k;
		res = 0;
		int maxCnt = 0;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> input[i][j];
				maxCnt = max(input[i][j], maxCnt);
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (input[i][j] == maxCnt) {
					//탐색
					dfs(i, j, 1, 1);
				}
			}
		}

		cout << "#" << tc << " " << res << endl;

	}
}

 

 

// java
import java.util.Scanner;
import java.io.FileInputStream;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
class pos {
    int x;
    int y;

    pos(int row, int col) {
        x = row;
        y = col;
    }

}

class posStack {

    pos[] stack;
    int len;
    int head;

    posStack(int x) {
        stack = new pos[x];
        head = -1;
        len = 0;
    }

    boolean isEmpty() {
        if (len == 0) return true;
        else return false;
    }

    pos peek() {
        return stack[head];
    }

    pos pop() {
        len--;
        return stack[head--];
    }

    void push(pos loc) {
        len++;
        stack[++head] = loc;
    }

    int getLen() {
        return len;
    }

}

class Solution
{

    static int longest = 0;

    // right, down, left, up
    static void dfs(int[][] map, posStack route, int x, int y, int N) {

        posStack move = new posStack(N*N);

        if (y + 1 < N && map[x][y+1] < map[x][y]) move.push(new pos(x, y+1));
        if (x + 1 < N && map[x+1][y] < map[x][y]) move.push(new pos(x+1, y));
        if (y - 1 >= 0 && map[x][y-1] < map[x][y]) move.push(new pos(x, y-1));
        if (x - 1 >= 0 && map[x-1][y] < map[x][y]) move.push(new pos(x-1, y));

        while (!move.isEmpty()) {
            route.push(move.pop());
            dfs(map, route, route.peek().x, route.peek().y, N);
            route.pop();
        }

        longest = Math.max(longest, route.getLen());


    }


    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
		/*
		   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
		*/

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N;
            int K;

            N = sc.nextInt();
            K = sc.nextInt();

            int [][] map = new int[N][N];
            int highest = 0;
            posStack highPoints = new posStack(N*N);
            longest = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                        map[i][j] = sc.nextInt();
                    }
                }


            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    highest = Math.max(map[i][j], highest);
                }
            }


            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == highest) highPoints.push(new pos(i, j));
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int k = 1; k <= K; k++) {
                        for (int l = 0; l < highPoints.getLen(); l++) {

                            int x = highPoints.stack[l].x;
                            int y = highPoints.stack[l].y;
                            posStack route = new posStack(N*N);
                            route.push(new pos(x, y));

                            /*
                            if (i == 2 && j == 4 && k == 1 && l == 2) {
                                String debug = "Debug";
                                System.out.println(debug);
                            }
                            */

                            map[i][j] -= k;
                            dfs(map, route, x, y, N);
                            map[i][j] += k;

                        }



                    }
                }
            }


            System.out.println("#" + (test_case) + " " + longest);

        }
    }
}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제