글 읽기 - 1987알파벳 반례 부탁드립니다/

skj2393 2년 전 0

한 시간 정도 1987 게시판 돌아다니면서 반례 적용시켜 봤는데 못 찾겠습니다.
방문한지 검사하는 것은 알파벳 지나온 걸로 알 수 있으니깐 따로 배열을 만들지 않았습니다.
이미 밟은 알파벳인지는 대문자가 26개이기 때문에 비트연산으로 해결하려고 하였습니다.
깊이 우선으로 해결하고 있으며 , 링크드 리스트에서 addFist, poll을 이용해 스택으로 활용하고 있습니다 .초기에 넣을 때는 그냥 넣구요

import java.util.LinkedList;
import java.util.Scanner;

class Location {
	int x;
	int y;
	int movePoint;
	int bitFlag;
	int dir;
	public Location(int curX, int curY, int movePoint, int bitFlag,int dir) {
		this.x = curX;
		this.y = curY;
		this.movePoint = movePoint;
		this.bitFlag = bitFlag;
		this.dir = dir;
	}

}

public class Main {
	final static int[] dx = { -1, 0, 0, 1 }; // 좌 , 하, 상, 우
	final static int[] dy = { 0, -1, 1, 0 };

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int R = sc.nextInt(); // 행 갯수
		int C = sc.nextInt(); // 열 갯수
		int[][] map = new int[R][C];

		for (int i = 0; i < R; i++) {
			String temp = sc.next();
			for (int j = 0; j < C; j++) {
				map[i][j] = temp.charAt(j) - 65; // 'A' == 65
			}
		}
		// 대문자 알파벳 갯수는 ? 26개 .....

		LinkedList<Location> stack = new LinkedList<>();
		int result = 1;

		stack.add(new Location(0, 0, 1, 1 << map[0][0],0));
		//따로 맵 안만들어도 방향과 이전 알파벳을 안 밟으면 가능
		while (!stack.isEmpty()) {
			Location cur = stack.poll();
		
			int row = cur.y;
			int col = cur.x;
			int dir = cur.dir;
			int point = cur.movePoint;
			int flag = cur.bitFlag;
			//System.out.println(cur.x +"," +cur.y);
			
			
			for (int i = dir; i < 4;) { // 좌하상우
				int nextY = row + dy[i];
				int  nextX= col + dx[i];
				
				if (nextX < C && nextX >= 0 && nextY < R && nextY >= 0) {
					if ((1 << map[nextY][nextX] & flag) == 0) {
						// 경계안넘고
						// 아직 안 밟은 알파벳
						// 단 산 쉬 관 비 논 ,
						stack.addFirst(new Location(row,col, point, flag,i+1));
						
						row = nextY;
						col = nextX;
						dir = 0;
						point = point+1;
						flag = 1 << map[nextY][nextX] | flag;
						i= 0;
						
						result = Math.max(result, point);
						//갈곳 위치찾았으면 현재 위치 저장하고 다음으로 가자 !
						continue;
					}
				}
				
				i++;
			}

		}
		System.out.print(result);
	}
}

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

문제

문제

출처

ICPC

1987알파벳 반례 부탁드립니다/

skj2393 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말