글 읽기 - 맞긴 맞았는데 이유가 궁금합니다

le_effort 4년 전 0

남들 코드 참고해서 풀긴 했는데 질문이 있습니다

1. dfs를 할 때 0,0~ n,m 까지 하는데

왜 처음껀 포함을 안하는가?

즉 0,0에서 dfs를 하면

0,0을 제외한 0,1 / 1,0 여기서부터 인접한 4칸으로만 가게 됩니다

왜냐면 dfs를 시작할때 0,0에 대한 sum을 넣어주지 않았고 바로 4방향으로 돌려버리니깐요

dfs가 level , x좌표 y좌표 , sum 일 때

0,0에서 dfs를 한 다하면

(1,0,0,map[0][0]) 을 하면 안되는 건가여?

그리고 첫번째 tc중

visited[3][0] , [3][1], [4][0], [4][1] 이 true 인 경우 출력을 하도록 해봤는데 이 경우 정사각형 모양의 테트로미오가 들어가야 정상일 법 한데

아무런 출력이 되지 않았고 즉 저 모양이 나오지 않았다는 소리죠

이 두가지 질문 답변 부탁드립니다 ㅠ

import java.io.*;
import java.util.*;
public class Main {
	static int n,m;
	static boolean visited[][];
	static int map[][];
	static int ans = 0;
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,1,-1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] t = br.readLine().split(" ");
		n = Integer.parseInt(t[0]);	//세로
		m = Integer.parseInt(t[1]);	//가로
		
		map = new int[n][m];
		visited = new boolean[n][m];
		for(int i=0; i<n; i++) {
			String[] tt = br.readLine().split(" ");
			for(int j=0; j<m; j++) {
				map[i][j]=Integer.parseInt(tt[j]);
			}
		}
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				dfs(i,j,0,0);
				//System.out.println(ans);
				int su = another_shape(i,j);
				//System.out.println(su);
				ans = Math.max(ans, su);
			}
		}
		System.out.println(ans);
	}
	public static int another_shape(int r, int c) {
		int max =0;
		int tmp=0;
		int cnt = 0;
		int[] nx_1 = {0,0,0,-1};
		int[] ny_1 = {0,1,2,1};
		int [] nx_2 = {0,1,1,2};
		int[] ny_2 = {0,0,1,0};
		int[] nx_3 = {0,1,1,2};
		int[] ny_3 = {0,0,-1,0};
		int[] nx_4= {0,0,0,1};
		int[] ny_4 = {0,1,2,1};
		for(int i=0; i<4; i++) {
			int nx = r+nx_1[i];
			int ny = c+ny_1[i];
			if(nx>=0 && ny>=0 && nx<n && ny<m) {
				tmp+=map[nx][ny];
				cnt++;
			}
		}
		if(cnt==4) {
			max=Math.max(max, tmp);
		}
		cnt=0;
		tmp=0;
		for(int i=0; i<4; i++) {
			int nx = r+nx_2[i];
			int ny = c+ny_2[i];
			if(nx>=0 && ny>=0 && nx<n && ny<m) {
				tmp+=map[nx][ny];
				cnt++;
			}
		}
		if(cnt==4) {
			max=Math.max(max, tmp);
		}
		cnt=0;
		tmp=0;
		for(int i=0; i<4; i++) {
			int nx = r+nx_3[i];
			int ny = c+ny_3[i];
			if(nx>=0 && ny>=0 && nx<n && ny<m) {
				tmp+=map[nx][ny];
				cnt++;
			}
		}
		if(cnt==4) {
			max=Math.max(max, tmp);
		}
		cnt=0;
		tmp=0;
		for(int i=0; i<4; i++) {
			int nx = r+nx_4[i];
			int ny = c+ny_4[i];
			if(nx>=0 && ny>=0 && nx<n && ny<m) {
				tmp+=map[nx][ny];
				cnt++;
			}
		}
		if(cnt==4) {
			max=Math.max(max, tmp);
		}
		cnt=0;
		tmp=0;
		return max;
	}
	public static void dfs(int r, int c ,int level, int sum) {
		if(level == 4) {
			
			ans=Math.max(ans, sum);
			return ;
		}
		for(int i=0; i<4; i++) {
			int nx = r+dx[i];
			int ny = c+dy[i];
			if(nx>=0 && ny>=0 && nx<n && ny<m) {
				if(!visited[nx][ny]) {
					visited[nx][ny]=true;
					//System.out.println(map[nx][ny]);
					dfs(nx,ny,level+1,sum+map[nx][ny]);
					visited[nx][ny]=false;
				}
			}
		}
	}
}
class Point{
	int x;
	int y;
	Point(int x, int y){
		this.x=x;
		this.y=y;
	}
}

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

문제

문제

출처

ICPC

맞긴 맞았는데 이유가 궁금합니다

le_effort 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말