글 읽기 - 고수형님들께.

mduddns 4년 전 0

샘플이랑 질문게시판에 있는 코드도 다 돌려봤는데 답은 맞게 나옵니다...

어떤 부분에서 잘못한 것인지 모르곘습니다....

반례 주시면 정말 감사하겠습니다. 거리가 같은 것중에서 왼쪽에 위치한거... y값 좌표가 작은걸 우선순위로 해서 정렬한후 처리하였습니다...

고수형님들 부탁드립니다.

건강하십쇼.

코드를 더럽게 짜서 죄송합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int m;
	static int D;
	static int[][] map;
	static int[] arr;
	static boolean[] visited;
	static List<Node>[] list;
	static Node[] node;
	static List<Node> enemy;
	static Set<Node> enemy2;
	static int max=Integer.MIN_VALUE;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		list = new List[3];
		node = new Node[3];
		map = new int[n][m];
		arr = new int[m];
		visited = new boolean[m];
		enemy = new LinkedList<>();
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j]==1) {
					enemy.add(new Node(i,j));
				}
			}
		}
		comb(0,0);
		System.out.println(max);
		
	}
	
	public static void comb(int c, int d) {
		if(c==3) { //궁수 3개 뽑았을때.
			int cnt=0;
			for(int i=0; i<m; i++) {
				if(visited[i]) {
					node[cnt++] = new Node(n, i);
					list[cnt-1] = new LinkedList<>();
				}
				if(cnt==3) {
					break;
				}
			}
			int tanswer=0;
			enemy2 = new LinkedHashSet();
			for(Node t : enemy) {
				enemy2.add(new Node(t.x,t.y)); //초기 적의 위치 담음.
			}
			while(true) {
				for(Node t : enemy2) {
					if(node[0].distance(t.x, t.y)<=D) { //각 궁수위치에서 공격가능한거 각 궁수별 리스트에 담음.
						list[0].add(new Node(t.x,t.y,node[0].distance(t.x, t.y)));
					}
					if(node[1].distance(t.x, t.y)<=D) {
						list[1].add(new Node(t.x,t.y,node[1].distance(t.x, t.y)));
					}
					if(node[2].distance(t.x, t.y)<=D) {
						list[2].add(new Node(t.x,t.y,node[2].distance(t.x, t.y)));
					}
				}
				for(int i=0; i<3; i++) {
					if(list[i].size()!=0) {
						Collections.sort(list[i]); // 가장 먼저 공격할거로 정렬하고 리스트에서 제거.
						Node t = list[i].remove(0);// 리스트에서 제거한 노드를 enemy셋에서 제거
						if(enemy2.contains(t)) {
							enemy2.remove(t);
							tanswer++;
						}
					}
				}
				List<Node> tempList = new LinkedList<>();
				for(Node t : enemy2) { //enemy셋의 x좌표를 +1해주기위해 옴겨담음
					tempList.add(t);
				}
				enemy2.clear();
				for(Node t : tempList) { //아직 제거되지 않은 적들중에 한칸 밑으로 내려올수 있는것만 다시 담음.
					if(t.x+1<n) {
						enemy2.add(new Node(t.x+1,t.y));
					}
				}
				int t2 = enemy2.size();
				if(t2==0) {
					max = Math.max(tanswer, max);
					
					return;
				}
				for(int i=0; i<3; i++) {
					list[i].clear();
				}
			}
			
		}
		else {
			for(int i=d; i<m; i++) {
				if(!visited[i]) {
					visited[i] = true;
					comb(c+1,i+1);
					visited[i] = false;
				}
			}
		}
	}
}


class Node implements Comparable<Node>{
	int x;
	int y;
	int d;
	Node(int x, int y){
		this.x=x;
		this.y=y;
		this.d=0;
	}
	Node(int x, int y,int d){
		this.x=x;
		this.y=y;
		this.d=d;
	}
	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		if(this.d==o.d) {//거리가 같은 적중에서 더 왼쪽에 있는 적... y값이 더 작은 적...
			
			return (this.y<o.y)? -1: 1;
		}
		else {
			return this.d-o.d;
		}
	}
	
	int distance(int x, int y) {
		return Math.abs(this.x-x) + Math.abs(this.y-y);
	}
	
	@Override
	public int hashCode() {
		// TODO Auto-generated method stub
		return Integer.hashCode(this.x+this.y);
	}
	
	@Override
	public boolean equals(Object obj) {
		// TODO Auto-generated method stub
		Node t = (Node)obj;
		if(t.x==this.x && this.y==t.y) {
			return true;
		}
		else {
			return false;
		}
	}
}

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

문제

문제

출처

ICPC

고수형님들께.

mduddns 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말