글 읽기 - 86%까지 갔는데 실패합니다... 반례가 무엇일까요...

iloveelsa 2년 전 0

3시간 동안 붙잡아도 답이 안 나와서 도움 요청해봅니다.

우선 코드가 더러워서 죄송합니다.

기본적으로 DFS를 사용하고 클래스와 HashSet을 사용해 이미 한 번 사용한 간선은 제외하고 탐색합니다.

칸이 사라지는 건 cnt에 1씩 더해서 cnt보다 큰 쪽으로만 이동할 수 있게 구현을 했고, pop으로 빠질 때 cnt를 다시 복구하는 방식입니다.

종료 조건은 플레이어가 다음 이동할 수가 n에 도달하거나 넘으면 1을 출력, 스택이 다 비어버리면 0을 출력하도록 했습니다.

계속 86%에서 실패하니까 손을 못 놓겠네요... HashSet 대신 ArrayList를 사용하면 시간초과가 뜹니다. hashCode() 문제인가 싶어서 hashCode() 메서드를 다양하게 정의해봐도 86%에서 실패합니다.

바쁘신 와중에도 봐주셔서 감사합니다.

import java.io.*;
import java.util.*;

public class Main {
	static int[] dy = { -1, 1 };
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		HashSet<Vertex> visited = new HashSet<Vertex>();
		boolean[][] map = new boolean[2][n];
		String s1 = br.readLine();
		String s2 = br.readLine();
		for (int i = 0; i < n; i++) {
			if (s1.charAt(i) == '1') {
				map[0][i] = true;
			}
			if (s2.charAt(i) == '1') {
				map[1][i] = true;
			}
		}
		ArrayDeque<int[]> stack = new ArrayDeque<int[]>();
		stack.push(new int[] {0, 0});
		int cnt = 0;
		while (!stack.isEmpty()) {
			int[] now = stack.peek();
			int x = now[0];
			int y = now[1];
			boolean flag = false;
			if (y + k >= n || y + 1 >= n) {
				System.out.println(1);
				return;
			}
			for (int i = 0; i < 2; i++) {
				Vertex v = new Vertex(x, y, x, y + dy[i]);
				if (y + dy[i] >= 0 && map[x][y + dy[i]] && !visited.contains(v) && y + dy[i] > cnt) {
					visited.add(v);
					stack.push(new int[] {x, y + dy[i]});
					flag = true;
					cnt++;
					break;
				}
			}
			Vertex v = new Vertex(x, y, (x + 1) % 2, y + k);
			if (!flag && map[(x + 1) % 2][y + k] && !visited.contains(v) && y + k > cnt) {
				visited.add(v);
				stack.push(new int[] {(x + 1) % 2, y + k});
				flag = true;
				cnt++;
			}
			if (!flag) {
				cnt--;
				stack.pop();
			}
		}
		System.out.println(0);
		br.close();
	}
}
class Vertex {
	int startX;
	int startY;
	int endX;
	int endY;
	public Vertex(int startX, int startY, int endX, int endY) {
		this.startX = startX;
		this.startY = startY;
		this.endX = endX;
		this.endY = endY;
	}
	@Override
	public int hashCode() {
		return this.startX * 1000 + this.startY * 100 + this.endX * 10 + this.endY;
	}
	@Override
	public boolean equals(Object obj) {
		Vertex other = (Vertex) obj;
		return this.startX == other.startX && this.startY == other.startY && this.endX == other.endX && this.endY == other.endY;
	}
}

azaraks 2년 전 0

BFS로 하면 해당 지점만 visited에 남기면 되니 Vertex가 필요없습니다.

iloveelsa 2년 전 0

azaraks

아 제가 잘못 생각했었네요. 생각해보니까 굳이 들렸던 곳을 빙 돌아서 들릴 필요가 없어서 간선을 저장하는 것이 아니라 그냥 visited로 해도 되는 거였습니다. DFS로 visited 체크해도 되더라구요. 다만, 위 코드에서는 그게 문제가 아니었고 다른 곳을 바꿔서 풀었습니다! 도와주셔서 감사합니다.

dudwls901 1년 전 0

어떻게 해결하셨나요?

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

문제

문제

출처

ICPC

86%까지 갔는데 실패합니다... 반례가 무엇일까요...

iloveelsa 2년 전 0

azaraks 2년 전 0

iloveelsa 2년 전 0

azaraks

dudwls901 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말