글 읽기 - 1109번 섬 반례 찾는 것좀 도와주세요 ㅠㅠ

rhksdlr134 3년 전 0

제가 작성한 코드는 아래와 같고, 예제와 몇 가지 테스트케이스를 만들었을 때 통과를 했습니다.

하지만 미처 체크하지 못하고 있는 부분이 있는 것 같아 반례찾는 것을 조금 도와주시기를 바라며 글을 남깁니다..ㅠㅠ

작성한 로직은 아래와 같습니다.

1. BFS로 섬마다 번호 붙이기

2. (0, 0) 노드에서 바다를 탐색하며 마주친 섬의 노드를 저장해두기

3. 마주친 섬으로부터 다시 탐색을 해서, 섬 내부의 바다 탐색하기

4. DFS로 섬 높이 계산하기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Island1109 {

	static int N;
	static int M;
	static int dy[] = {-1, 0, 1, 0, 1, 1, -1, -1};
	static int dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
	static char map[][];
	static int max = 0;
	static int heights[] = new int[51];
	static int island[][];
	static boolean visited[][];
	static Map<Integer, List<Integer>> nodes = new HashMap<>();
	
	static void setIsland(Point start, int no) {
		Queue<Point> q = new LinkedList<Point>();
		q.add(start);
		island[start.y][start.x] = no;
		while(!q.isEmpty()) {
			Point now = q.poll();
			for(int i = 0; i < 8; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];
				if(ny < 0 || nx < 0 || ny > N + 1 || nx > M + 1 || map[ny][nx] == '.' || island[ny][nx] != 0) continue;
				island[ny][nx] = no;
				q.add(new Point(ny, nx));
			}
		}
	}
	
	static void findSea(Point start, int no) {
		Queue<Point> q = new LinkedList<Point>();
		Map<Integer, List<Point>> islands = new HashMap<Integer, List<Point>>();
		q.add(start);
		visited[start.y][start.x] = true;
		while(!q.isEmpty()) {
			Point now = q.poll();
			for(int i = 0; i < 4; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];
				if(ny < 0 || nx < 0 || ny > N + 1 || nx > M + 1 || visited[ny][nx]) continue;
				// 바다라면 Keep going
				if(map[ny][nx] == '.') {
					visited[ny][nx] = true;
					q.add(new Point(ny, nx));
					continue;
				}
				// 섬이네?
				if(island[ny][nx] == no) { // 현재 도는 거랑 같은 섬이면 방문
					visited[ny][nx] = true;
					q.add(new Point(ny, nx));
				} else { // 다른 섬이면 다음에 방문할 노드로 추가
					List<Point> list = (islands.containsKey(island[ny][nx]))? islands.get(island[ny][nx]) : new ArrayList<Point>();
					list.add(new Point(ny, nx));
					islands.put(island[ny][nx], list);
				}
			}
		}
		
		for(Integer i : islands.keySet()) {
			nodes.get(no).add(i);
			for(Point p : islands.get(i)) {
				if(!visited[p.y][p.x]) {
					findSea(p, i);
				}
			}
		}
	}
	
	static int getHeight(int node) {
		int ret = 0;
		for(Integer next : nodes.get(node)) {
			ret = Math.max(heights[node], getHeight(next) + 1);
		}
		if(node != 0) {
			heights[ret]++;
			max = Math.max(max, ret);
		}
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N + 2][M + 2];
		island = new int[N + 2][M + 2];
		visited = new boolean[N + 2][M + 2];
		
		List<Point> islands = new ArrayList<Point>();
		for(int i = 0; i < N + 2; i++) {
			String str = null;
			if(i > 0 && i < N + 1)
				str = br.readLine();
			for(int j = 0; j < M + 2; j++) {
				if(i == 0 || j == 0 || i == N + 1 || j == M + 1)
					map[i][j] = '.';
				else if(i >= 1 && j >= 1 && i <= N && j <= M) {
					map[i][j] = str.charAt(j - 1);
					if(map[i][j] == 'x') islands.add(new Point(i, j));
				}
			}
		}
		
		if(islands.size() == 0) {
			bw.write("-1");
		} else {
			// 1. Set Island No
			int islandNo = 0;
			for(Point p : islands) {
				if(island[p.y][p.x] == 0)
					setIsland(p, ++islandNo);
			}
			
			for(int i = 0; i <= islandNo; i++)
				nodes.put(i, new ArrayList<>());
			
			// 2. Sea
			findSea(new Point(0, 0), 0);
			
			// 3. Get Height
			for(Integer node : nodes.get(0)) {
				getHeight(node);
			}
			for(int i = 0; i <= max; i++) {
				bw.write(heights[i] + " ");
			}
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
	
	static class Point {
		int y;
		int x;
		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

}

dnfl182 2년 전 1

11 10

xxxxxxxxxx

x........x

x.xxxxxx.x

x.x....x.x

x.x.xx.x.x

x.x....x.x

x.xxxxxx.x

x........x

x.x.xx.x.x

x........x

xxxxxxxxxx

정답: 4 1 1

rhksdlr134 2년 전 0

감사합니다! 덕분에 재귀로 높이를 처리하던 부분에서 오류가 있음을 찾을 수 있었습니다.

조금 더 꼼꼼하게 코드를 봤어야 하는데... 다시한번 감사드립니다~!

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

문제

문제

출처

ICPC

1109번 섬 반례 찾는 것좀 도와주세요 ㅠㅠ

rhksdlr134 3년 전 0

dnfl182 2년 전 1

rhksdlr134 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말