글 읽기 - 틀렸다고 나오네요..

kkw9219 4년 전 0

여러가지 Case로 돌려봤는데.. 틀리다고 나오네요...

뭐가 틀렸는 지 모르겠네요... ㅜㅜ

어떤 벗어난 Case가 있을런지요?

혹시 푸신 분 중께서는 댓글 부탁드립니다.

.......................

..OOOOOOOOO.OOOOOOOOO..

.O...........O.......O.

.O.OOOOO.O.O.O...X...O.

.O.O...O.O...O.......O.

.O.O...O.O.O.O.XXXXX.O.

.O.O.X.O.O...O.X.X.X.O.

.O.O...O.O.O.O.X...X.O.

.O.OOOOO.O...O.XXXXX.O.

.O.......O...O.......O.

.OOOOOOOOOOOOOOOOOOOOO.

....................

........OOOOOOOOOO..

..OOOOOO.O.......O..

..O.....O.OOOOO..O..

..O..OOOO..O..O..O..

..O.OO..O.....O..O..

..O.O...O..O..O..O..

..O.O.O.O.....O..O..

..O.O...O.....O..O..

..O.O...O..O..O..O..

..O.OO.O......O..O..

..O....OOOOOOOO..O..

..OOOOO..........O..

.......OOOOOOOOOOO..

....................

......................

.OOOOOOOOOOOOOOOOOOOO.

.O.......O..O.......O.

.O.XXXXX.O..O...X...O.

.O.X...X.O..O.......O.

.O.X...X.O..O.XXXXX.O.

.O.X.X.X.O..O.X.X.X.O.

.O.X...X.O..O.X...X.O.

.O.XXXXX.O..O.XXXXX.O.

.O.......O..O.......O.

.OOOOOOOOOOOOOOOOOOOO.

......................

.......................

..OOOOOOOOOOOOOOOOOOO..

.O.......O...........O.

.O.XXXXX.O.X.O...X...O.

.O.X...X.O...O.......O.

.O.X...X.O.X.O.XXXXX.O.

.O.X.X.X.O...O.X.X.X.O.

.O.X...X.O.X.O.X...X.O.

.O.XXXXX.O...O.XXXXX.O.

.O.......O...O.......O.

.OOOOOOOOOOOOOOOOOOOOO.

.......................

..OOOOOOO....OOOOOOOOO.

.O.......O...O.......O.

.O.OOOOO.O...O.XXXXX.O.

.O.O...O.O...O.X...X.O.

.O.O.X.O.O...O.X.X.X.O.

.O.O...O.O...O.X...X.O.

.O.OOOOO.O...O.XXXXX.O.

.O.......O...O.......O.

..OOOOOOO....OOOOOOOOO.

.......................

package fibo;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Island16000 {
	static int N, M;
	static final int n_ = 20002;
	static final int nm_ = 4000001;
	static char [][] a;
	static int [][] vst;
	static int [] con;
	static int []dx = new int [] { 0, 0, -1, 1 };
	static int []dy = new int [] { -1, 1, 0, 0 };
	static HashSet<Integer> [] list;
	static int num;
	static int []vOrder;
	static int tOrder;
	static boolean []is_cutP;
	static Stack<Integer> stk = new Stack<Integer>(); 
	static int [] isSum;
	static int [] depth;	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		/*
		 * 
자가용 비행기로 태평양 한복판을 비행하던 튜브는, 연료 부족으로 외딴섬 한가운데에 불시착하고 말았다! 
다행히도, 튜브는 섬 근방의 지역에 대한 정보가 전부 나와있는 N × M 격자 모양의 지도를 발견하였다.
튜브가 발견한 지도에서, 격자의 각 셀은 전부 바다이거나 육지이며, 최외곽에 있는 셀들은 모두 바다이다. 
엄밀하게 정의해서, 격자의 각 셀은 (x, y) (1 ≤ x ≤ N, 1 ≤ y ≤ M) 형태의 좌표로 표현되며, 
x = 1, x = N, y = 1, y = M 중 하나의 식이라도 만족하는 셀 (x, y)는 바다임이 보장된다. 
모든 육지 셀은 어떠한 섬의 일부분인데, 두 육지 셀이 인접하다면 (한 면을 맞닿고 있다면) 이들은 하나의 섬으로 간주된다. 
다른 말로, (x, y)와 (x+1, y)가 모두 육지 셀이면 둘은 같은 섬에 속하고, 
(x, y)와 (x, y+1)이 모두 육지 셀이면 이 둘 역시 같은 섬에 속한다.
튜브는 현재 위치에서 뗏목을 주웠고, 이 뗏목을 타고 저 멀리 망망대해로 먼 여정을 떠날 예정이다. 
튜브는 임의의 셀에서 인접한 4방향의 셀로 이동할 수 있으며, 이동 시에는 해당 셀이 육지인지 바다인지의 여부는 중요하지 않다 
(뗏목을 주웠으니까!). 튜브의 목표는 현재의 위치에서 이러한 이동을 통해 저 멀리 바다에서 연료를 찾아 돌아오는 것이다.
하지만 튜브는 두 가지 문제점에 봉착해 있다. 첫 번째 문제는, 튜브가 불시착한 지역에 있는 섬 중 하나의 섬에는 
오리를 잡아먹으려 하는 무서운 사냥꾼들이 살고 있다. 튜브가 현재 있는 섬은 안전함을 확인했으나, 
만약 탈출 시 사냥꾼이 있는 섬을 지나야 만 한다면 튜브는 큰 위험에 처하게 된다! 
두 번째 문제는, 튜브가 현재 지도 상의 어느 섬에 있는지를 알지 못한다는 것이다. 
튜브가 있는 섬은 최외곽의 바다와 바로 인접해있는 편리한 곳일 수도 있으나, 다른 섬들에 층층이 둘러싸인 위험한 곳일 수도 있다.
튜브는 지도상의 모든 섬에 대해서 해당 섬이 안전한지 위험한지를 알고 싶어 한다. 
어떠한 섬 S 가 위험하다는 것은, S 에서 최외곽 셀로 가기 위해서 무조건 지나야 하는 S 와는 다른 섬 T 가 존재한다는 것이고, 
S 가 안전하다는 것은 S 가 위험하지 않다는 것을 뜻한다. 
튜브를 도와서, 지도상에 있는 섬들 중 안전한 섬이 무엇이고 위험한 섬이 무엇인지 알려주자!

입력
첫 번째 줄에는 격자의 크기 N, M 이 공백으로 구분되어 주어진다. (3 ≤ N, M ≤ 2,000)
이후 N 개의 줄에 길이 M 의 문자열이 주어진다. 
이 중 i 번째 줄의 j 번째 문자는 (i, j) 셀의 상태를 나타내는데, 
만약 이 문자가 '#'이라면 해당 셀은 육지이고, '.'이라면 해당 셀은 바다이다. 
문자열 내에서 이 외의 문자는 주어지지 않음이 보장된다. 
격자 안에는 하나 이상의 육지 셀이 존재함이 보장된다.
9 7
.......
.#####.
.#...#.
.#...#.
.#.#.#.
.#...#.
.#...#.
.#####.
.......		 */
		
		System.setIn(new FileInputStream("Is_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer str = new StringTokenizer(br.readLine());
		N = Integer.parseInt(str.nextToken());
		M = Integer.parseInt(str.nextToken());
		
		list = new HashSet[N*M+1];
		a =  new char [N+1][M+1];
		vst = new int [N+1][M+1];
		con = new int [N*M+1];
		vOrder = new int[N*M+1];
		
		is_cutP = new boolean[N*M+1];
		isSum = new int [N*M+1];
		depth = new int [N*M+1];	
		
		
		for(int i = 0; i < N*M+1; i++) {
			list[i] = new HashSet<Integer>();
		}
		for(int i = 1; i <= N; i++) {
			String s = br.readLine();
			for(int j = 0; j < M; j++) {
				a[i][j+1] = s.charAt(j);
			}			
		}
		num = 0;
		process();
		dfs(1, -1);
		
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= M; j++) {
				if(a[i][j] == '.') {
					bw.write(".");
					//System.out.print(".");					
				}
				else {
					int num_1 = vst[i][j];
					if(con[num_1] == 1 && vOrder[num_1]!=1) {
						bw.write("X");
						//System.out.print("X");							
					}
					else {
						bw.write("O");
						//System.out.print("O");	
					}					
				}				
			}
			bw.newLine();
			//System.out.println();
		}
		bw.flush();
		bw.close();
	}
	static int dfs(int v, int p) {
		//System.out.printf("Call DFS(curr:%d, prev:%d)\n", v, p);
		vOrder[v] = ++tOrder;
		int minLow = vOrder[v];
		//System.out.printf("Stack PUSH(%d)\n", v);
		stk.add(v);
		
		for(int n : list[v]) {
			if(n == p)
				continue;
			
			if(vOrder[n] != 0) {
				minLow = Math.min(minLow, vOrder[n]);
				continue;
			}
			int Low = dfs(n, v);
			if(p != -1 && Low >= vOrder[v] && isSum[v] == 1) {
				//System.out.printf("ArcPoint(Island):%d\n", v);
				while(!stk.isEmpty() && stk.lastElement() != v) {
					con[stk.lastElement()] = 1;
					//System.out.printf("Stack Pop:%d\n",stk.lastElement());
					stk.pop();					
				}				
			}
			minLow = Math.min(minLow, Low);		
		}
		return minLow;	
	}
	static void process() {		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= M; j++) {
				if(vst[i][j] != 0) {
					continue;
				}
				go(i, j, ++num);
			}
		}
		for (int i = 1; i <= N; i++) 
			for (int j = 1; j <= M; j++)
				if (a[i][j] == '#') 
					isSum[vst[i][j]] = 1;	
	}	
	static void go(int y, int x, int num_1) {
		vst[y][x] = num_1;
		for(int i = 0; i < 4; i++) {
			int ny = y+dy[i], nx = x+dx[i];
			if(1 <= ny && ny <= N && 1 <= nx && nx <= M 
					&& a[y][x] == a[ny][nx] && vst[ny][nx]==0) {
				go(ny, nx, num_1);
			}
			else if(1 <= ny && ny <= N && 1 <= nx && nx <= M 
					&& a[y][x] != a[ny][nx] && vst[ny][nx]!=0) {				
				list[num_1].add(vst[ny][nx]);
				list[vst[ny][nx]].add(num_1);	
			}
		}		
	}	
}

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

문제

문제

출처

ICPC

틀렸다고 나오네요..

kkw9219 4년 전 0

.......................

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말