글 읽기 - 시간초과 나는데 한번만 확인해주실래요..ㅜㅜ

dhseo89 5년 전 0

ㅗ 모양을 제외한 경우는 dfs탐색했습니다

ㅗ모양은 방법이 생각이 안나 for문 돌면서 더했습니다...

예시는 다맞는데 시간초과나서 도무지 모르겠네요

고수님들 알려주세요...ㅜㅜ

import java.util.Scanner;

public class Tetris {
	
	static int N,M;
	static int map[][];
	static int result = Integer.MIN_VALUE;
	static int temp;
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	
	static int tx1[] = {0,0,-1};
	static int ty1[] = {1,2,1};
	static int tx2[] = {1,2,1};
	static int ty2[] = {0,0,1};
	static int tx3[] = {0,0,1};
	static int ty3[] = {1,2,1};
	static int tx4[] = {0,-1,1};
	static int ty4[] = {1,1,1};	
	static boolean visited[][];
	static int dd;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N= sc.nextInt();
		M= sc.nextInt();
		map = new int[N][M];
		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		tetris();
		tetris2();
//		System.out.println("dd "+dd);
		System.out.println(result);
	}
	//ㅗ 검사 ㄱ
	private static void tetris2() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				for (int k = 1; k <= 4; k++) { //타입
					temp = 0;
					temp += map[i][j];
					plus(i,j,k);
				}
			}
		}
	}

	private static void plus(int x, int y, int k) {
//		dd++;
		if(k == 1) {
			for (int i = 0; i < tx1.length; i++) {
				int nx = x + tx1[i];
				int ny = y + ty1[i];
				if(nx <0 || nx > N-1 || ny <0 || ny > M-1) return;
				temp += map[nx][ny];
			}
		}else if(k ==2) {
			for (int i = 0; i < tx2.length; i++) {
				int nx = x + tx2[i];
				int ny = y + ty2[i];
				if(nx <0 || nx > N-1 || ny <0 || ny > M-1) return;
				temp += map[nx][ny];				
			}
			
		}else if(k==3) {
			for (int i = 0; i < tx3.length; i++) {
				int nx = x + tx3[i];
				int ny = y + ty3[i];
				if(nx <0 || nx > N-1 || ny <0 || ny > M-1) return;
				temp += map[nx][ny];					
			}
		}else if(k==4) {
			for (int i = 0; i < tx4.length; i++) {
				int nx = x + tx4[i];
				int ny = y + ty4[i];
				if(nx <0 || nx > N-1 || ny <0 || ny > M-1) return;
				temp += map[nx][ny];					
			}
		}
		result = Math.max(temp, result);
	}
	
	private static void tetris() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited = new boolean[N][M];
				temp = 0;
				temp+=map[i][j];
				visited[i][j] = true;
				dfs(i,j,1);
				temp-=map[i][j];
				visited[i][j] = false;
			}
		}
	}
	
	private static void dfs(int x, int y, int cnt) {
		if(cnt == 4) {
			result = Math.max(temp, result);
			return;
		}
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx < 0 || nx> N-1 || ny <0 || ny>M-1 || visited[nx][ny]) continue;
			temp += map[nx][ny];
			visited[nx][ny] = true;
			dfs(nx,ny,cnt+1);
			temp -= map[nx][ny];
			visited[nx][ny] = false;
		}
	}
}

jy6145 5년 전 0

아무 제약조건 없이 DFS를 사용하면 중복해서 도형을 검사하기때문에 시간초과가 발생합니다.

저같은 경우에는 DFS 시작점과 인접한 지점 1곳을 선택하고, 남은 2점을 선택하기 위해 DFS를 돌립니다.

그리고 모든 DFS가 방문하면 그 지점을 다시 방문 못하게 막았습니다.

이해가 잘 안되시면 아래 제가 작성한 소스 참고해주세요!

https://github.com/jy6145/algorithm/blob/master/BaekjoonOnlineJudge/BOJ14500.java

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 나는데 한번만 확인해주실래요..ㅜㅜ

dhseo89 5년 전 0

jy6145 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말