글 읽기 - 2박3일째 반례를 찾고 있어요...!

starsuzi 5년 전 0

안녕하세요....

이 문제로 2박3일을 풀고 있는데, 문제에서 주어진 모든 테스트케이스와 게시판에 올라와 있는 반례들은 잘 맞춥니다!!!그리고 간단한 테스트케이스도 잘 맞추더라구용..

최대 M개를 선택하는 것이기에 M개 보다 적게 선택하면 치킨거리가 최소가 되지 않을 것이라 판단하여 치킨집이 M개로 선택될 때 답을 계산하도록 구현했습니다!!

저는 dfs로 치킨집 조합을 찾아 배열에 담은 후, 집의 좌표를 담은 배열과 2중 for문을 통해 최소 거리를 찾고 이 값들 중 다시 최소 값을 찾도록 구현했는데 틀렸다고 뜨네요ㅠㅜ

고수님들 도와주세요ㅠㅠㅠㅠ

import java.util.Scanner;

public class Main{

	static int N, M;
	static int[][] map;
	static int[][] visited;
	static int[] chickDis;
	static int House;
	static ChickenPosition[] ChickenLocation;
	static ChickenPosition ChickenPos;
	static ChickenPosition HousePos;
	static ChickenPosition[] HouseLocation;
	static int result = Integer.MAX_VALUE;
	static int tmp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

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

		map = new int[N+1][N+1];
		visited = new int[N+1][N+1];

		for (int y = 1; y < N+1; y++) {
			for (int x = 1; x < N+1; x++) {
				map[y][x] = sc.nextInt();
			}
		}

		House = countHouse();

		ChickenLocation = new ChickenPosition[M]; 
		HouseLocation = new ChickenPosition[House];


		chickDis = new int[House];

		int count = 0;
		for (int i = 1; i < N+1; i++) {
			for (int j = 1; j < N+1; j++) {
				if(map[i][j]==1) {
					HouseLocation[count] = new ChickenPosition(i, j);
					count++;
				}
			}
		}



		for (int y = 1; y < N+1; y++) {
			for (int x = 1; x < N+1; x++) {
				if(map[y][x] == 2) {
					dfs(y,x,0);
				}
			}
		}

		for (int i = 0; i < ChickenLocation.length; i++) {
			//	System.out.println(ChickenLocation[i]);
		}
		System.out.println(result);

	}


	static void dfs(int currentY, int currentX, int depth) {

		//0. 도달?
		if(depth == M-1) {

			// 치킨집 좌표를 배열에 담는다
			ChickenLocation[depth] = new ChickenPosition(currentY, currentX);

			tmp = chickenDistance(ChickenLocation);

			if(result>tmp) {
				result = tmp;
			}

			return;


		}

		//1. 방문체크
		visited[currentY][currentX] = 1;
		//치킨집 좌표를 배열에 담는다
		ChickenLocation[depth] = new ChickenPosition(currentY, currentX);

		//2. 연결된길
		for (int y = 1; y < N+1; y++) {
			for (int x = 1; x < N+1; x++) {
				//3. 갈수있는길
				if(map[y][x] == 2 && visited[y][x] != 1) {
					//4. 간다
					dfs(y,x,depth+1);
				}
			}

		}
	}

	static int countHouse() {
		int count = 0;

		for (int y = 1; y < N+1; y++) {
			for (int x = 1; x < N+1; x++) {
				if(map[y][x] == 1) {
					count++;
				}
			}
		}
		return count;
	}


	static int chickenDistance(ChickenPosition[] chickLo) {
		int temp;
		int dis = Integer.MAX_VALUE;

		for (int i = 0; i < HouseLocation.length; i++) {
			dis = Integer.MAX_VALUE;
			for (int j = 0; j < M; j++) {

				temp = (Math.abs(HouseLocation[i].Y -chickLo[j].Y)+Math.abs(HouseLocation[i].X -chickLo[j].X));

				if(temp<dis) {
					dis = temp;
				}
			}
			chickDis[i] = dis;

		}
		int sum = 0;
		for (int i = 0; i < chickDis.length; i++) {
			sum+=chickDis[i];
		}
		return sum;
	}

}
class ChickenPosition{

	int Y;
	int X;

	public ChickenPosition(int Y, int X) {
		super();
		this.Y = Y;
		this.X = X;
	}

	@Override
	public String toString() {
		return "ChickenPosition [Y=" + Y + ", X=" + X + "]";
	}

}

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

문제

문제

출처

ICPC

2박3일째 반례를 찾고 있어요...!

starsuzi 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말