글 읽기 - 자바 hashMap 비교?가 궁금합니다. 제발..

5ffy 3년 전 0

아래 33번째줄을 boolean[][] 으로 선언해서 해결하긴 했습니다.

그런데 hashMap으로 했을 때 왜 안되는지가 궁금합니다. 제 머리로는 key값이 같은 값이면 해시 함수를 적용해도 똑같은 값이 나올거라 생각했습니다. 그래서 "x,y" 꼴로 키를 지정해서 boolean을 대체해주더라도 해결이 가능할거라 생각했습니다. 그런데 답이 틀리게 나오더라고요.. (아래 틀린 코드도 첨부하겠습니다.)

1. 잘못된 곳이 어느 부분인지 명확합니다. boolean을 hashMap으로 바꾸니 안됩니다. 그런데 이유가 뭘까요?ㅜ

2. 자바는 이렇게 2차원 좌표값을 hashMap으로 잘 처리하지 않나요? 만약 처리한다면 어떤식으로 처리하나요?

import java.util.Map;
import java.util.Scanner;

// visit
public class Main {
	// data
	// board로 점수 확인(가는 방향에따라 이차원으로 처리)
	// 말 정보(x, y, 도착했는지)
	// visited로 board에 있는지 확인하려 했는데... board가 저렇게 있을땐 visited 크기 어떻게 선언해야함? 최대로?
	static final int BOARD[][] = new int [][]{ 
			{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40},
			{10, 13, 16, 19},	
			{20, 22, 24},		
			{30, 28, 27, 26},	
			{40},
			{25, 30, 35, 40},
	};
	static class Horse {
		int x, y;
		boolean arrived;
		Horse(int x, int y, boolean arrived) {
			this.x = x;
			this.y = y;
			this.arrived = arrived;
		}
		// 디버깅용
		public String toString() {
			return x + ", " + y + ", " + arrived;
		}
	}
	static int dice[];
	static Horse horse[];
	static boolean visit[][] = new boolean[BOARD.length][BOARD[0].length];	//최대로 잡음
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		dice = new int[10];
		horse = new Horse[4];
		for(int i = 0; i < 4; i++) horse[i] = new Horse(0, 0, false);
		for(int i = 0; i < 10; i++) {
			dice[i] = sc.nextInt();
		}
		System.out.println(solve(0, 0));
		sc.close();
	}
	
	// function
	// 완탐
	// 말 이동, 방향 바뀌면 들어가는거 처리
	static int max(int a, int b) {
		return a > b ? a : b;
	}
	static void deepCopy(Horse[] src, Horse[] dest) {
		for(int i = 0; i < dest.length; i++) {
			dest[i] = new Horse(src[i].x, src[i].y, src[i].arrived);
		}
	}
	static void deepCopy(boolean[][] src, boolean[][] dest) {
		for(int i = 0; i < src.length; i++) {
			dest[i] = src[i].clone();
		}
	}
	// 이렇게 해도 되고 생성자 이용해서 해도 됨 new HashMap<String, Boolean>(src); 이런식으로
	// 둘 다 알아두기
	static void deepCopy(Map<String, Boolean>src, Map<String, Boolean>dest) {
		for(Map.Entry<String, Boolean> entry: src.entrySet()) {
			dest.put(entry.getKey(), entry.getValue());
		}
	}
	static int move(Horse h, int d) {
		int nx = h.x;
		int ny = h.y + d;
		if(BOARD[nx].length <= ny) {
			// 도착
			if(nx == 0 || nx == 5) {
				visit[h.x][h.y] = false;
				h.arrived = true;
				return 0;
			} else {
				ny = ny - BOARD[nx].length; 
				nx = 5;
				if(BOARD[nx].length <= ny) {
					visit[h.x][h.y] = false;
					h.arrived = true;
					return 0;
				}
			}
		}
		// 방향 꺾이는거 처리
		if(nx == 0) {
			if(ny % 5 == 0) {
				nx = (ny) / 5;
				ny = 0;
				if(nx == 4) {
					nx = 5;
					ny = BOARD[nx].length-1;
				}
			}
		}
		// 이미 그 위치에 말이 있으면 종료
		if (visit[nx][ny]) {
			return -1;
		}
		// 이동할거라서 지움, x, y 좌표 갱신, visited 갱신
		visit[h.x][h.y] = false;
		h.x = nx;
		h.y = ny;
		visit[nx][ny] = true;
		return BOARD[nx][ny];
	}
	static int solve(int pos, int sum) {
		int res = 0;
		if(pos == dice.length) {
			return sum;
		}
//		Map<String, Boolean> tempVisited = new HashMap<>();
//		deepCopy(visited, tempVisited);
		Horse tempHorse[] = new Horse[4];
		boolean[][] tempVisit = new boolean[visit.length][visit[0].length];
		deepCopy(visit, tempVisit);
		deepCopy(horse, tempHorse);
		for(int i = 0; i < 4; i++) {
			if(horse[i].arrived) continue;
			int add = move(horse[i], dice[pos]);
//			System.out.println(pos + " " + i + " " + horse[i] + " " + add);
			if (add == -1) continue;		//말 있는경우는 다음말로
			res = max(res, solve(pos+1, sum+add));
//			deepCopy(tempVisited, visited);
			deepCopy(tempVisit, visit);
			deepCopy(tempHorse, horse);
		}
		// 10, 10, 10, 10, ... 이면 pos 끝에 못닿음 그거 처리해주려고 중간의 sum과도 비교해줌 
		res = max(res, sum);
		return res;
	}
}

//틀린 코드---------------------------------------------------------
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// visit
public class Main {
	// data
	// board로 점수 확인(가는 방향에따라 이차원으로 처리)
	// 말 정보(x, y, 도착했는지)
	// visited로 board에 있는지 확인하려 했는데... board가 저렇게 있을땐 visited 크기 어떻게 선언해야함? 최대로?
	static final int BOARD[][] = new int [][]{ 
			{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40},
			{10, 13, 16, 19},	
			{20, 22, 24},		
			{30, 28, 27, 26},	
			{40},
			{25, 30, 35, 40},
	};
	static class Horse {
		int x, y;
		boolean arrived;
		Horse(int x, int y, boolean arrived) {
			this.x = x;
			this.y = y;
			this.arrived = arrived;
		}
		// 디버깅용
		public String toString() {
			return x + ", " + y + ", " + arrived;
		}
	}
	static int dice[];
	static Horse horse[];
//	static boolean visit[][] = new boolean[BOARD.length][BOARD[0].length];	//최대로 잡음
	static Map<String, Boolean> visit = new HashMap<>(); 
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		dice = new int[10];
		horse = new Horse[4];
		for(int i = 0; i < 4; i++) horse[i] = new Horse(0, 0, false);
		for(int i = 0; i < 10; i++) {
			dice[i] = sc.nextInt();
		}
		System.out.println(solve(0, 0));
		sc.close();
	}
	
	// function
	// 완탐
	// 말 이동, 방향 바뀌면 들어가는거 처리
	static int max(int a, int b) {
		return a > b ? a : b;
	}
	static void deepCopy(Horse[] src, Horse[] dest) {
		for(int i = 0; i < dest.length; i++) {
			dest[i] = new Horse(src[i].x, src[i].y, src[i].arrived);
		}
	}
	static void deepCopy(boolean[][] src, boolean[][] dest) {
		for(int i = 0; i < src.length; i++) {
			dest[i] = src[i].clone();
		}
	}
	// 이렇게 해도 되고 생성자 이용해서 해도 됨 new HashMap<String, Boolean>(src); 이런식으로
	// 둘 다 알아두기
	static void deepCopy(Map<String, Boolean>src, Map<String, Boolean>dest) {
		for(Map.Entry<String, Boolean> entry: src.entrySet()) {
			dest.put(entry.getKey(), entry.getValue());
		}
	}
	static int move(Horse h, int d) {
		int nx = h.x;
		int ny = h.y + d;
		if(BOARD[nx].length <= ny) {
			// 도착
			if(nx == 0 || nx == 5) {
				visit.remove(h.x+","+h.y);
				h.arrived = true;
				return 0;
			} else {
				ny = ny - BOARD[nx].length; 
				nx = 5;
				if(BOARD[nx].length <= ny) {
					visit.remove(h.x+","+h.y);
					h.arrived = true;
					return 0;
				}
			}
		}
		// 방향 꺾이는거 처리
		if(nx == 0) {
			if(ny % 5 == 0) {
				nx = (ny) / 5;
				ny = 0;
				if(nx == 4) {
					nx = 5;
					ny = BOARD[nx].length-1;
				}
			}
		}
		// 이미 그 위치에 말이 있으면 종료
		if(visit.containsKey(nx+","+ny)) return -1;
		// 이동할거라서 지움, x, y 좌표 갱신, visited 갱신
		visit.remove(h.x+","+h.y);
		h.x = nx;
		h.y = ny;
		visit.put(nx+","+ny, true);
		return BOARD[nx][ny];
	}
	static int solve(int pos, int sum) {
		int res = 0;
		if(pos == dice.length) {
			return sum;
		}
//		Map<String, Boolean> tempVisited = new HashMap<>();
//		deepCopy(visited, tempVisited);
		Horse tempHorse[] = new Horse[4];
//		boolean[][] tempVisit = new boolean[visit.length][visit[0].length];
		Map<String, Boolean> tempVisit = new HashMap<>();
		deepCopy(visit, tempVisit);
		deepCopy(horse, tempHorse);
		for(int i = 0; i < 4; i++) {
			if(horse[i].arrived) continue;
			int add = move(horse[i], dice[pos]);
//			System.out.println(pos + " " + i + " " + horse[i] + " " + add);
			if (add == -1) continue;		//말 있는경우는 다음말로
			res = max(res, solve(pos+1, sum+add));
//			deepCopy(tempVisited, visited);
			deepCopy(tempVisit, visit);
			deepCopy(tempHorse, horse);
		}
		// 10, 10, 10, 10, ... 이면 pos 끝에 못닿음 그거 처리해주려고 중간의 sum과도 비교해줌 
		res = max(res, sum);
		return res;
	}
}

exponential_e 3년 전 1

코드를 자세히 보진 않았지만 질문하신 2번 내용 기반으로 설명드리자면,

HashMap을 통해서 좌표를 표현할 수 있냐면, 그건 맞지만 key: x, value: y 이런식으로 표현할 수는 없습니다.

HashMap은 key의 중복을 허용하지 않기 때문인데요. 만약 아래와 같이 입력을 한다면,

Map<Integer, Integer> map = new HashMap<>();

map.put(1, 2);

map.put(1, 3);

해쉬맵에는 중복 key: 1로 인해 1, 3만 존재하게 됩니다. (이미지 참고해 주세요)

값이 누락되기 때문에 체크가 안되겠죠..

만약 굳이 맵으로 표현하시겠다면, key: (x * 10의 제곱수 + y), value: 1 이런식으로는 저장이 가능 할 것 같습니다. (key가 중복되지 않도록)

다른 방식으로는 말씀하신 boolean이나, class 선언해서 사용하는 것이 일반적인 듯 합니다.

5ffy 3년 전 0

와 정성 드려 답변해주셔서 감사합니다!

저는String 값으로 x + "," + y 이렇게 넣어서 좌표의key값이 중복되지 않도록 했습니다. (추가로 말씀해주신 방법대로 x * P + y (P는 나올 수 있는 y의 가장 큰 값) 이렇게도 했는데 똑같이 답아 나오질 않아서 고민중에 있습니다 ㅜㅜ )

map을 삭제하고 put하고 하는 과정에서 문제가 있는걸까요...?

exponential_e 3년 전 1

저도 혹시나해서 코드를 자세히 읽어보니.. key 구분은 확실하게 하신 것 같은데("," 이용해서 문자열로 바꾸셨네요. 엉뚱한 답변 죄송합니다 ㅠㅠ)

'map을 삭제하고 put하고 하는 과정에서 문제가 있는걸까요...?' 저도 이게 조금 의심이되서 출력해보면서 체크해보니.. 삭제했는데 다시 entry에 포함되어있는 경우가 있는데,

로직을 전반적으로 이해하진 못해서 정확한 문제는 모르겠네요.ㅠㅠ 혹시 맵에 boolean 값이 어떤 방식으로 쓰이는 건지 설명해주실 수 있나요?

exponential_e 3년 전 1

우선 예제 1 ~ 3번은 오답코드 265번째 줄 deepCopy 전에 아래 코드를 추가해 초기화 시켜주시면 잘 나옵니다.

visited에 있으면 안될 값이 존재했습니다..

따라서 재귀가 끝난 후 temp를 visited에 복사시 temp의 값만 존재해야할 것 같은데, 그 외에도 부수적인 값들이 visited에 존재해 잘못된 답을 출력한 것 같습니다.

4번 예제는 잘못된 답이 나오는데.. 어떤 문젠지 정확히는 모르겠네요.

(또한, HashMap에 boolean 값을 변경은 하는데 따로 쓰지 않으시는 것 같습니다. 이게 뭔가 어색한데.. 문제가 있는진 모르겠습니다.)

visited = new HashMap<>();

5ffy 3년 전 1

와 진짜 친절하시다... 진짜진짜 감사합니다 절받으세여 지금 계실거 같은 방향으로 그랜절하고있습니다

boolean은 그냥 null값 넣고 key값의 존재 유무로 확인하려 했었습니다!

삭제했는데 entry에 있는 경우를 주시하며 다시 디버깅 하면서 어디가 문젠지 찾아봐야 겠네요 ㅎㅎ

저녁 맛있게 드시고 행복한 주말 보내세요!! :)

exponential_e 3년 전 1

아.. 아닙니다 ㅎㅎ

대충 문제점은 찾긴했는데, 지금 4번 예제가 {5 5 5} 당 40씩 점수를 얻게되고 따라서 120 + (5, 1회 = 10) = 130의 값이 나오게됩니다.

근데 결과값이 50만 나오는거 보니.. 주사위 10개를 모두 쓰는 경우가 적용이 안되고 있는게 아닌가 싶네요..

특히, 해당 예제에서 아래 코드 부분이 작동하지 않습니다. (pos 값 최대: 4)

5ffy님도 좋은 주말 되시길 바랍니다~

if(pos == dice.length) {
    return sum;
}

5ffy 3년 전 1

시간내어 신경써주셔서 감사합니다 ㅜㅜ

exponential_e님 말 듣고 왜 없어도 될게 자꾸 있는 거지 고민하다가 찾았습니다!!

203 line deepcopy() 부분 문제였습니다! 아래처럼 초기화 시켜주고 복사해주니 잘 되네요!! :)

덕분에 암이 나았습니다 감사합니다 ㅎㅎㅎㅎ

엄청 친절하셔서 아까 해결이 잘 안된 상태인데도 기분 되게 좋았어요

복받으세요~~~~

static void deepCopy(Map<Integer, Boolean>src, Map<Integer, Boolean>dest) {
		dest.clear();
		for(Map.Entry<Integer, Boolean> entry: src.entrySet()) {
			dest.put(entry.getKey(), entry.getValue());
		}
}

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

문제

문제

출처

ICPC

자바 hashMap 비교?가 궁금합니다. 제발..

5ffy 3년 전 0

exponential_e 3년 전 1

5ffy 3년 전 0

exponential_e 3년 전 1

exponential_e 3년 전 1

5ffy 3년 전 1

exponential_e 3년 전 1

5ffy 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말