[백준온라인] 14500번 테트로미노

문제 : https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

문제요약 : 이어지는 4개의 정사각형 구간합의 최댓값 출력

입력	출력
4 ≤ N,M(크기) ≤ 500 1 ≤ [N][M] ≤ 1000	테트로미노가 놓인 칸의 합의 최댓값

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16352773	cbkpar	14500	맞았습니다!!	38684KB	668ms	Java	1199B

import java.io.*;

public class Main {

	static int[][] map;
	static int[][] move;
	static int n,m;
	static int score=0;
	static int[] dx = {0,0,1,-1}; //상하우좌
	static int[] dy = {1,-1,0,0};
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,j;
		String str = "";
		str = br.readLine();
		String[] arr = str.split(" ");
		n = Integer.parseInt(arr[0]);
		m = Integer.parseInt(arr[1]);
		map = new int[n][m];
		move = new int[n][m];
		for(i=0;i<n;i++) {
			str = br.readLine();
			arr = str.split(" ");
			for(j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(arr[j]);
			}
		}
		for(i=0;i<n;i++) {
			for(j=0;j<m;j++) {
				move[i][j]=1; // 해당구간 이동 불가 설정
				dfs(i,j,map[i][j],1);
				move[i][j]=0; // 해당구간 이동 가능 설정
			}
		}
		System.out.println(score);
	}

	static void dfs(int y, int x, int s, int k) {
		if(k==4) { // 4개의 정사각형 선택했을 경우
			score = Math.max(score, s); // 최대값 갱신 후 리턴
			return;
		}
		for(int i=0;i<4;i++) {
			if(y+dy[i]>=0&&y+dy[i]<n&&x+dx[i]>=0&&x+dx[i]<m&&move[y+dy[i]][x+dx[i]]==0) {
            //인덱스를 넘어가거나 이동이 가능한지 확인
				move[y+dy[i]][x+dx[i]]=1; //가능하다면 이동불가상태로 만듦
				dfs(y+dy[i],x+dx[i],s+map[y+dy[i]][x+dx[i]],k+1);
				if(k==2) dfs(y,x,s+map[y+dy[i]][x+dx[i]],k+1); // 2번째 블럭의 경우 2번째 블럭에서 다시체크
				move[y+dy[i]][x+dx[i]]=0; //다시 이동 가능하도록 설정
			}
		}
	}
}

 

JAVA - 배열을 쓰지 않고 상하좌우를 나눴을 때

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16352586	cbkpar	14500	맞았습니다!!	37348KB	568ms	Java	1438B

import java.io.*;

public class Main {

	static int[][] map;
	static int[][] move;
	static int n,m;
	static int score=0;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,j;
		String str = "";
		str = br.readLine();
		String[] arr = str.split(" ");
		n = Integer.parseInt(arr[0]);
		m = Integer.parseInt(arr[1]);
		map = new int[n][m];
		move = new int[n][m];
		for(i=0;i<n;i++) {
			str = br.readLine();
			arr = str.split(" ");
			for(j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(arr[j]);
			}
		}
		for(i=0;i<n;i++) {
			for(j=0;j<m;j++) {
				move[i][j]=1;
				dfs(i,j,map[i][j],1);
				move[i][j]=0;
			}
		}
		System.out.println(score);
	}

	static void dfs(int y, int x, int s, int k) {
		if(k==4) {
			score = Math.max(score, s);
			return;
		}
		if(y>0&&move[y-1][x]==0) {
			move[y-1][x]=1;
			dfs(y-1,x,s+map[y-1][x],k+1);
			if(k==2) dfs(y,x,s+map[y-1][x],k+1);
			move[y-1][x]=0;
		}
		if(y<n-1&&move[y+1][x]==0) {
			move[y+1][x]=1;
			dfs(y+1,x,s+map[y+1][x],k+1);
			if(k==2) dfs(y,x,s+map[y+1][x],k+1);
			move[y+1][x]=0;
		}
		if(x>0&&move[y][x-1]==0) {
			move[y][x-1]=1;
			dfs(y,x-1,s+map[y][x-1],k+1);
			if(k==2) dfs(y,x,s+map[y][x-1],k+1);
			move[y][x-1]=0;
		}
		if(x<m-1&&move[y][x+1]==0) {
			move[y][x+1]=1;
			dfs(y,x+1,s+map[y][x+1],k+1);
			if(k==2) dfs(y,x,s+map[y][x+1],k+1);
			move[y][x+1]=0;
		}
	}
}

 

배열을 쓰지 않고 if문으로 상하좌우를 나눴을 때 시간을 단축 할 수 있었음.

 

개선할 점 : 한 블럭에 대해서 중복해서 검사하는 회수가 적어도 2회 이상이므로 중복을 제거하면 시간을 2배이상 단축 할 수 있을 것으로 예상.

 

아래는 중복검사하는 과정(숫자는 순서)

1		4		1	4		4	3
2		3		2	3		1	2
3		2
4		1		3	2		2	1
				4	1		3	4