반응형
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
완전탐색에 대한 개념이 잘 안잡혀있어서 너무 어려웠던 문제이다.
참고한 블로그 - https://hanyeop.tistory.com/416
메모리 : 35972 KB
시간 : 736 ms
코드길이 : 2698 B
[내 코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int M;
static int[][] graph;
static boolean[][] isVisit;
static int max = Integer.MIN_VALUE;
//상하좌우 탐색 때 필요한 값 배열로 저장
static int[] x = {-1, 1, 0, 0};
static int[] y = {0, 0, -1, 1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new int[N][M];
//방문한 그래프를 표시해주는 용도
isVisit = new boolean[N][M];
//그래프 입력
for(int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
for(int m = 0; m < M; m++) {
graph[n][m] = Integer.parseInt(st.nextToken());
}
}
for(int n = 0; n < N; n++) {
for(int m = 0; m < M; m++) {
//true로 바꿔주며 시작점을 방문한 곳으로 바꿔줌
isVisit[n][m] = true;
solve(n, m, graph[n][m], 1);
isVisit[n][m] = false;
}
}
sb.append(max);
System.out.print(sb);
}
//탐색시작점의 row, column, 탐색한 부분의 총값, count == 탐색한 길이
static void solve(int row, int column, int sum, int count) {
//테트로미노 완성 시 ( count == 4 ) 최댓값 비교 후 저장
if(count == 4) {
max = Math.max(max, sum);
return;
}
//상하좌우 탐색
for(int i = 0; i < 4; i++) {
int currentRow = row + x[i];
int currentColumn = column + y[i];
//범위를 벗어나면 예외처리
if(currentRow < 0 || currentRow >= N || currentColumn < 0 || currentColumn >= M) {
continue;
}
//아직 방문하지 않은 곳으로 탐색
if(!isVisit[currentRow][currentColumn]) {
//ㅜ모양 테트리스는 2번째에서 한 번 더 탐색을 해줘야 하기 때문에
if(count == 2) {
//현재(2번째)도 방문했다고 표시해준 후
isVisit[currentRow][currentColumn] = true;
//다시 시작점에서 나머지 하,좌,우를 탐색해주면 ㅜ의 모양이 됨.
solve(row, column, sum + graph[currentRow][currentColumn], count + 1);
isVisit[currentRow][currentColumn] = false;
}
//현재 그래프를 탐색했다고 표시해준 후
isVisit[currentRow][currentColumn] = true;
solve(currentRow, currentColumn, sum + graph[currentRow][currentColumn], count + 1);
isVisit[currentRow][currentColumn] =false;
}
}
}
}
1등 코드
메모리 : 15828 KB
시간 : 168 ms
코드길이 : 5988 B
[1등 코드]
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class Main {
static int M, N, answer, array [][];
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
int N = in.nextInt();
int M = in.nextInt();
array = new int[M+6][N+6];
for(int i = 3; i<N+3; i++){
for(int j = 3; j<M+3; j++){
array[j][i] = in.nextInt();
}
}
for(int i=0; i<M+3; i++){
for(int j=0; j<N+3; j++){
dfs(i, j);
}
}
}
private static void dfs(int a, int b){
// 직선 (세로 놓기)
int sum=0;
sum += array[a][b];
sum += array[a+1][b];
sum += array[a+2][b];
sum += array[a+3][b];
if(answer<sum){
answer = sum;
}
// 직선 (가로 놓기)
sum=0;
sum += array[a][b];
sum += array[a][b+1];
sum += array[a][b+2];
sum += array[a][b+3];
if(answer<sum){
answer = sum;
}
// 네모
sum=0;
sum += array[a][b];
sum += array[a+1][b];
sum += array[a+1][b+1];
sum += array[a][b+1];
if(answer<sum){
answer = sum;
}
// ㄴ // 왼상단시작 오른 하단 종료. (반시계방향)
sum=0;
sum += array[a][b];
sum += array[a+1][b];
sum += array[a+2][b];
sum += array[a+2][b+1];
if(answer<sum){
answer = sum;
}
// ㄴ case // 왼상단시작 오른 하단 종료. (반시계방향)의 대칭.
sum=0;
sum += array[a][b+1];
sum += array[a+1][b+1];
sum += array[a+2][b+1];
sum += array[a+2][b];
if(answer<sum){
answer = sum;
}
// ㄴ // 왼하단시작 오른 상단 종료.
sum=0;
sum += array[a][b];
sum += array[a+1][b];
sum += array[a][b+1];
sum += array[a][b+2];
if(answer<sum){
answer = sum;
}
// ㄴ // 왼하단시작 오른 상단 종료.
sum=0;
sum += array[a][b];
sum += array[a+1][b+2];
sum += array[a][b+1];
sum += array[a][b+2];
if(answer<sum){
answer = sum;
}
// ㄴ // 왼상단시작 오른 하단 종료 (시계방향)
sum=0;
sum += array[a][b];
sum += array[a][b+1];
sum += array[a+1][b+1];
sum += array[a+2][b+1];
if(answer<sum){
answer = sum;
}
// ㄴ // 왼상단시작 오른 하단 종료 (시계방향) 의 대칭
sum=0;
sum += array[a][b];
sum += array[a][b+1];
sum += array[a+1][b];
sum += array[a+2][b];
if(answer<sum){
answer = sum;
}
// ㄴ // 오른 상단시작 왼 하단 종료
sum=0;
sum += array[a][b+2];
sum += array[a+1][b+2];
sum += array[a+1][b+1];
sum += array[a+1][b];
if(answer<sum){
answer = sum;
}
// ㄴ // 오른 상단시작 왼 하단 종료 의 대칭
sum=0;
sum += array[a+1][b+2];
sum += array[a+1][b+1];
sum += array[a+1][b];
sum += array[a][b];
if(answer<sum){
answer = sum;
}
// ㄴㄱ // 왼상단시작 오른 하단 종료
sum=0;
sum += array[a][b];
sum += array[a+1][b];
sum += array[a+1][b+1];
sum += array[a+2][b+1];
if(answer<sum){
answer = sum;
}
// ㄴㄱ // 오른 상단시작 하단 종료.
sum=0;
sum += array[a][b+2];
sum += array[a][b+1];
sum += array[a+1][b+1];
sum += array[a+1][b];
if(answer<sum){
answer = sum;
}
// ㄴㄱ // 왼하단시작 오른 상단 종료.
sum=0;
sum += array[a+2][b];
sum += array[a+1][b];
sum += array[a+1][b+1];
sum += array[a][b+1];
if(answer<sum){
answer = sum;
}
// ㄴㄱ // 왼상단시작 오른 하단 종료. (ㄱㄴ꼴)
sum=0;
sum += array[a][b];
sum += array[a][b+1];
sum += array[a+1][b+1];
sum += array[a+1][b+2];
if(answer<sum){
answer = sum;
}
// ㅗ // ㅜ
sum=0;
sum += array[a][b];
sum += array[a][b+1];
sum += array[a][b+2];
sum += array[a+1][b+1];
if(answer<sum){
answer = sum;
}
// ㅗ // ㅓ
sum=0;
sum += array[a][b+1];
sum += array[a+1][b+1];
sum += array[a+2][b+1];
sum += array[a+1][b];
if(answer<sum){
answer = sum;
}
// ㅗ // ㅗ
sum=0;
sum += array[a+1][b];
sum += array[a+1][b+1];
sum += array[a+1][b+2];
sum += array[a][b+1];
if(answer<sum){
answer = sum;
}
// ㅗ // ㅏ
sum=0;
sum += array[a][b];
sum += array[a+1][b];
sum += array[a+2][b];
sum += array[a+1][b+1];
if(answer<sum){
answer = sum;
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}반응형
'백준 > 완전탐색' 카테고리의 다른 글
| [백준] 5052 : 전화번호 목록 (0) | 2024.11.07 |
|---|---|
| [백준] 15686 : 치킨 배달 (JAVA) (0) | 2024.09.26 |
| [백준] 1062 : 가르침 (JAVA) (0) | 2024.09.20 |