SW 역량테스트 - [백준] 테트로미노 문제 풀이/해답/코드 (C++ / JAVA)

---

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

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

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

 

---

문제 링크 : www.acmicpc.net/problem/14500

해답 코드 : 

 

// c++

#include<stdio.h>

int T, N, M;
int input[501][501];
int visit[501][501] = { 0, };
int answer = 0;

typedef struct point {
	int x, y;
}point;

// STACK 정의
point STACK[5];
int top = -1;
point pop() {
	return STACK[top--];
}
void push(int x, int y) {
	STACK[++top].x = x;
	STACK[top].y = y;
}

// 상하좌우 dx, dy
int dArr[][4] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };

void dfs(int n, int m, int sum, int depth) {

	sum += input[n][m];

	// 종료조건
	if (depth == 1) {
		if (sum > answer)
			answer = sum;
		return;
	}

	// stack에 추가함
	push(n, m);
	visit[n][m] = 1;

	for (int k = 0; k <= top; k++) { // STACK에 담긴 모든 원소들을 하나씩 탐색
		for (int a = 0; a < 4; a++) {  // 각 각의 STACK 원소의 상하좌우 원소 : (newX, newY)

			int newX = STACK[k].x + dArr[a][0];
			int newY = STACK[k].y + dArr[a][1];

			// 좌표 범위 검사
			if (newX >= N || newY >= M || newX < 0 || newY < 0)
				continue;

			if (visit[newX][newY] == 0)
				dfs(newX, newY, sum, depth - 1);
		}
	}

	// stack에서 삭제함
	visit[n][m] = 0;
	pop();

	return;
}

int main() {

	int temp;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {

			scanf("%d", &temp);
			input[i][j] = temp;
		}


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

			dfs(i, j, 0, 4);
		}

	printf("%d", answer);
}

 

 

// java

import java.util.Scanner;
import java.io.*;
import java.util.Stack;

class pos {
    int x;
    int y;

    pos(int i, int j) {
        x = i;
        y = j;
    }

    public int get_x() {
        return x;
    }
    public int get_y() {
        return y;
    }
}

public class Main {

    static int N, M;
    //static int[][] paper = new int[505][505];
    static int max_sum = -9999;

    static Stack<pos> dfs_stack = new Stack<>();
    //static Stack<pos> temp_stack = new Stack<>();

    static void dfs(int[][] paper) {

        int result = 0;
        Stack<pos> temp_stack = new Stack<>();

        // terminate when the stack size is 4
        if (dfs_stack.size() == 4) {
            for (pos each:dfs_stack) {
                result += paper[each.get_x()][each.get_y()];
            }
            max_sum = Math.max(max_sum, result);
            return;
        }


        // find the way out
        if (!dfs_stack.empty()) {

            for (pos each:dfs_stack) {

                //pos temp = dfs_stack.peek();
                int temp_x = each.get_x();
                int temp_y = each.get_y();

                if (temp_x + 1 < N) temp_stack.push(new pos(temp_x+1, temp_y));
                if (temp_y + 1 < M) temp_stack.push(new pos(temp_x, temp_y+1));
                if (temp_x - 1 >= 0) temp_stack.push(new pos(temp_x-1, temp_y));
                if (temp_y - 1 >= 0) temp_stack.push(new pos(temp_x, temp_y-1));
            }

        }

        while (!temp_stack.empty()) {
            boolean duplicate = false;

            pos temp = temp_stack.pop();
            for (pos each:dfs_stack) {
                if (each.get_x() == temp.get_x() && each.get_y() == temp.get_y()) {
                    duplicate = true;
                    break;
                }
            }
            if (duplicate) continue;

            dfs_stack.push(temp);
            dfs(paper);
            dfs_stack.pop();
        }


    }

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

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

        int[][] paper = new int[N][M];

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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                while (!dfs_stack.isEmpty()) {
                    dfs_stack.pop();
                }

                // initialize stack for each loop when the loop starts
                dfs_stack.push(new pos(i, j));
                dfs(paper);
            }
        }


        System.out.println(max_sum);

        sc.close();

    }

}

 

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

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

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