문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq
💻 문제 풀이 : C++
✔ 내 풀이
- 임의로 한 곳을 1~k만큼 공사
😢시간복잡도 O(n^4). . . ❗ - 완전탐색 DFS
#include <iostream>
#include <vector>
using namespace std;
int MAP[9][9] = { 0, };
int used[9][9] = { 0, };
int dr[4] = { 0, 0, -1, 1 };
int dc[4] = {-1, 1, 0, 0 };
int start = 0, ans;
int N, K;
struct Coord {
int row;
int col;
};
vector<Coord> v_start;
void Init() {
ans = -1;
start = -1;
v_start.clear();
}
void dfs(int row, int col, int cnt)
{
used[row][col] = 1;
for (int i = 0; i < 4; i++)
{
int next_row = row + dr[i];
int next_col = col + dc[i];
if (next_row < 0 || next_col < 0 || next_row >= N || next_col >= N) continue;
if (used[next_row][next_col]) continue;
if (MAP[next_row][next_col] < MAP[row][col])
dfs(next_row, next_col, cnt + 1);
}
if (cnt > ans) ans = cnt;
used[row][col] = 0;
}
void find_start()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (start < MAP[i][j])
start = MAP[i][j];
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (MAP[i][j] == start)
{
used[i][j] = 1;
v_start.push_back({ i, j });
}
}
}
}
void make_road()
{
int row, col;
for (int i = 0; i < v_start.size(); i++)
{
row = v_start[i].row;
col = v_start[i].col;
if (MAP[row][col] == start) dfs(row, col, 1);
}
}
void Solve() {
find_start();
make_road();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 1; k <= K; k++)
{
MAP[i][j] -= k;
make_road();
MAP[i][j] += k;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int T;
cin >> T;
for (int test_case = 1; test_case <= T; test_case++)
{
cin >> N >> K;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> MAP[i][j];
Init();
Solve();
cout << "#" << test_case << " " << ans << endl;
}
return (0);
}
✔ 다른 고수님의 풀이 #1
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int y;
int x;
};
int MAP[8][8];
int maxLen = -2134567890;
int n, k;
int maxHeight = -2134567890;
int minHeight = 2134567890;
int visited[8][8];
vector<Node> path;
int flag = 0;
void dfs(int y, int x) {
int len = path.size();
if (maxLen < len) maxLen = len;
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if (visited[ny][nx] != 0) continue;
if (MAP[y][x] <= MAP[ny][nx] ) {
if (flag == 0) {
for (int j = 1; j <= k; j++) {
if (MAP[y][x] > MAP[ny][nx] - j) {
int temp = MAP[ny][nx];
visited[ny][nx] = 1;
path.push_back({ ny, nx });
MAP[ny][nx] = MAP[ny][nx] - j;
flag = 1;
dfs(ny, nx);
flag = 0;
MAP[ny][nx] = temp;
path.pop_back();
visited[ny][nx] = 0;
}
}
}
continue;
}
visited[ny][nx] = 1;
path.push_back({ ny, nx });
dfs(ny, nx);
path.pop_back();
visited[ny][nx] = 0;
}
}
int main() {
int t = 0;
cin >> t;
for (int testcase = 0; testcase < t; testcase++) {
cin >> n >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> MAP[i][j];
if (maxHeight < MAP[i][j]) {
maxHeight = MAP[i][j];
}
if (minHeight > MAP[i][j]) {
minHeight = MAP[i][j];
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (maxHeight == MAP[i][j]) {
visited[i][j] = 1;
path.push_back({ i, j });
dfs(i, j);
visited[i][j] = 0;
path.pop_back();
}
}
}
cout <<"#" <<testcase+1 << " "<< maxLen << "\n";
// 초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
MAP[i][j] = 0;
visited[i][j] = 0;
}
}
maxHeight = -2134567890;
minHeight = 2134567890;
maxLen = -2134567890;
flag = 0;
path.clear();
}
return 0;
}📌 memo
✔ void 반환 형태의 재귀함수 구현
void dfs(int y, int x) {
int len = path.size();
if (maxLen < len) maxLen = len;
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if (visited[ny][nx] != 0) continue;
if (MAP[y][x] <= MAP[ny][nx] ) {
if (flag == 0) {
for (int j = 1; j <= k; j++) {
if (MAP[y][x] > MAP[ny][nx] - j) {
int temp = MAP[ny][nx];
visited[ny][nx] = 1;
path.push_back({ ny, nx });
MAP[ny][nx] = MAP[ny][nx] - j;
flag = 1;
dfs(ny, nx);
flag = 0;
MAP[ny][nx] = temp;
path.pop_back();
visited[ny][nx] = 0;
}
}
}
continue;
}
visited[ny][nx] = 1;
path.push_back({ ny, nx });
dfs(ny, nx);
path.pop_back();
visited[ny][nx] = 0;
}
}✔ Idea💡 !!
- 공사를 얼마나 해야할까??
=> (지금 좌표 높이 - 1)만 해주면 됨
=> 적절한 K를 찾기위한 노력 필요없음!! 👍😁
✔ 다른 고수님의 풀이 #2
#include <iostream>
using namespace std;
const int MAX = 10;
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
int n, k;
int mountain[MAX][MAX];
int check[MAX][MAX];
int maxLength;
int makeRoad(int x, int y, int height, bool didDig)
{
int length = 1;
for (int i = 0; i < 4; i++)
{
int tx = x + dx[i];
int ty = y + dy[i];
if (tx < 0 || tx >= n || ty < 0 || ty >= n) continue;
if (check[tx][ty] != 0) continue;
check[tx][ty] = 1;
if (height > mountain[tx][ty])
{
length = max(length, makeRoad(tx, ty, mountain[tx][ty], didDig) + 1);
}
else if (height > mountain[tx][ty] - k && didDig == false)
{
length = max(length, makeRoad(tx, ty, height - 1, true) + 1);
}
check[tx][ty] = 0;
}
return length;
}
void solve()
{
static int test = 1;
cin >> n >> k;
int maxHeight = -1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> mountain[i][j];
if (mountain[i][j] > maxHeight)
maxHeight = mountain[i][j];
}
}
maxLength = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (mountain[i][j] == maxHeight)
{
check[i][j] = 1;
maxLength = max(maxLength, makeRoad(i, j, mountain[i][j], false));
check[i][j] = 0;
}
}
}
cout << "#" << test << " ";
cout << maxLength << endl;
test++;
}
int main(void)
{
int T;
cin >> T;
for (int t = 1; t <= T; t++)
{
solve();
}
return 0;
}📌 memo
✔ integer 반환형태의 재귀함수로 구현하기
int DFS(int x, int y, int height, bool didDig)
{
int length = 1;
for(int i = 0 ; i < 4 ; i++)
{
int tx = x + dx[i];
int ty = y + dy[i];
if (tx < 0 || tx >= n || ty < 0 || ty >= n) continue;
if (check[tx][ty] != 0) continue;
check[tx][ty] = 1;
if (height > mountain[tx][ty])
{
length = max(length, makeRoad(tx, ty, mountain[tx][ty], didDig) + 1);
}
else if (height > mountain[tx][ty] - k && didDig == false)
{
length = max(length, makeRoad(tx, ty, height - 1, true) + 1);
}
check[tx][ty] = 0;
}
return length;
}✔ Idea💡 !!
- MAP 전체 완전탐색
=> 최고점에서만 탐색하기 👍😁
✔ 다른 고수님의 풀이 #3
#include <iostream>
#include <vector>
#define MAX_N 9
using namespace std;
struct Coord {
int row;
int col;
};
int n, k;
int MAP[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
vector<Coord> pos;
void Input() {
cin >> n >> k;
int maxHeight = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> MAP[i][j];
if (MAP[i][j] > maxHeight) {
pos.clear();
}
if (MAP[i][j] >= maxHeight) {
pos.push_back({ i, j });
maxHeight = MAP[i][j];
}
}
}
}
int dfs(Coord now, int flag, int height) { // 현재 좌표, 공사 여부, 지금 좌표 높이
int ret = 1; // 초기값, 일단 1개 포함
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };
for (int i = 0; i < 4; i++) {
int nr = now.row + dr[i], nc = now.col + dc[i];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (visited[nr][nc]) continue;
visited[nr][nc] = true;
if (height > MAP[nr][nc]) {
ret = max(ret, dfs({ nr, nc }, flag, MAP[nr][nc]) + 1);
}
else if (flag == 0 && height > MAP[nr][nc] - k) {
ret = max(ret, dfs({ nr, nc }, 1, height - 1) + 1);
} // 다음 좌표의 높이가 현재좌표 높이 이상인 경우 -> 공사
visited[nr][nc] = false;
}
return ret;
}
int Solution() {
int ret = 0;
for (int i = 0; i < pos.size(); i++) {
Coord st = pos[i]; // 등산로의 시작점
visited[st.row][st.col] = true;
ret = max(ret, dfs(st, 0, MAP[st.row][st.col]));
visited[st.row][st.col] = false;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
Input();
cout << "#" << t << " " << Solution() << "\n";
}
return 0;
}📌 memo
✔ Coord 구조체 사용
struct Coord {
int row;
int col;
}
vector<Coord> pos;
✔ 최고점 찾기
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < N ; j++) {
cin >> MAP[i][j];
if (MAP[i][j] > maxHeight) {
pos.clear();
}
if (MAP[i][j] >= maxHeight) {
pos.push_back({ i, j });
maxHeight = MAP[i][j];
}
}
}📌 memo 😊
공부방