백준 14500 - 테트로미노(C++)

문제 링크입니다 https://www.acmicpc.net/problem/14500

14500번: 테트로미노

삼성 SW 역량 테스트 기출 문제입니다.

DFS를 이용하는 것이 핵심이였습니다.

 

문제 조건

출력 예시

 

위 도형중에서 'ㅗ' 모양의 보라색 도형을 제외한다면 나머지 모두는 상하좌우 4번을 연속해서 이동한다면 모두 구할 수 있습니다.

 

 

문제 접근 방법 

1. 모든 칸마다 DFS를 통해서 상하좌우 이동한다.

2. 4번 이동한다면, 지금까지의 최댓값과 비교한다.

3. 조건에 맞다면 'ㅗ' 모양으로 나올 수 있는 값들을 확인후 비교한다.

 

 

문제 접근 방법 - 1번 + 2번

void dfs(int x, int y, int sum, int cnt) {
    if (cnt == 4) {
        max_point = max(max_point, sum);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
            if (check[xx][yy] == 0) {
                check[xx][yy] = 1;
                dfs(xx, yy, sum + point[xx][yy], cnt + 1);
                check[xx][yy] = 0;
            }
        }
    }
}

dfs() 함수에 좌표, 지금까지의 합, 이동횟수를 받았습니다. 

이동 횟수가 4일때는, 지금까지 합을 최댓값과 비교해, 큰 값을 받았습니다.

 

 

문제 접근 방법 - 3번

void shape_1(int x, int y) {
    int sum = 0;
    sum += point[x][y] + point[x][y + 1] + point[x][y - 1] + point[x + 1][y];
    max_point = max(max_point, sum);
}
void shape_2(int x, int y) {
    int sum = 0;
    sum += point[x][y] + point[x][y+1] + point[x][y-1] + point[x-1][y];
    max_point = max(max_point, sum);
}
void shape_3(int x, int y) {
    int sum = 0;
    sum += point[x][y] + point[x][y - 1] + point[x + 1][y] + point[x - 1][y];
    max_point = max(max_point, sum);
}
void shape_4(int x, int y) {
    int sum = 0;
    sum += point[x][y] + point[x][y + 1] + point[x + 1][y] + point[x - 1][y];
    max_point = max(max_point, sum);
}

'ㅗ' 모양으로는 나올 수 있는 경우가 4가지 입니다. 이들을 조건에 따라 전부 확인했습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int N, M;
int point[501][501];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int check[501][501];
int max_point;

void dfs(int x, int y, int sum, int cnt) {
    if (cnt == 4) {
        max_point = max(max_point, sum);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
            if (check[xx][yy] == 0) {
                check[xx][yy] = 1;
                dfs(xx, yy, sum + point[xx][yy], cnt + 1);
                check[xx][yy] = 0;
            }
        }
    }
}

void shape_1(int x, int y) {
    int sum = 0;
    sum += point[x][y] + point[x][y + 1] + point[x][y - 1] + point[x + 1][y];
    max_point = max(max_point, sum);
}
void shape_2(int x, int y) {
    int sum = 0;
    sum += point[x][y] + point[x][y+1] + point[x][y-1] + point[x-1][y];
    max_point = max(max_point, sum);
}
void shape_3(int x, int y) {
    int sum = 0;
    sum += point[x][y] + point[x][y - 1] + point[x + 1][y] + point[x - 1][y];
    max_point = max(max_point, sum);
}
void shape_4(int x, int y) {
    int sum = 0;
    sum += point[x][y] + point[x][y + 1] + point[x + 1][y] + point[x - 1][y];
    max_point = max(max_point, sum);
}

void solve() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            check[i][j] = 1;
            dfs(i, j, point[i][j], 1);
            if (j - 1 >= 1 && j + 1 <= M && i + 1 <= N) shape_1(i, j);
            if (j - 1 >= 1 && j + 1 <= M && i - 1 >= 1) shape_2(i, j);
            if (i - 1 >= 1 && j - 1 >= 1 && i + 1 <= N) shape_3(i, j);
            if (i + 1 <= N && i - 1 >= 1 && j + 1 <= M) shape_4(i, j);
            check[i][j] = 0;
        }
    }
    cout << max_point;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> point[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!