메뉴 닫기

[BOJ] 2667 단지번호붙이기

2667번: 단지번호붙이기 (acmicpc.net)

접근방식

연결여부만 파악하면 된다고 생각했고, 이때 연속된 단지의 경우 개수를 세서 이를 자료구조에 넣고 정렬하였다.
그리고 시작점을 정하기 위해 selectOne이라는 메서드를 이용해 이전에 방문한 i,j 값에서부터 시작해서 다음 Node를 리턴하거나 모두 방문하면 null을 리턴하도록 하였다.
그리고 while문을 이용해 이 조건을 반복적으로 체크하였다.

연결여부 파악방식은 DFS, BFS 편한거 사용하면 될 것 같다.
글을 적으면서 생각해보니 BFS를 위한 visited배열이 필요가 없다고 생각이 되었다.
map에 이미 0과 1로 표시되어있기 때문에, 이 조건만 이용하면 굳이 visited 배열을 쓰지 않더라도 탐색을 할 수 있을 것 같다.
바로 코드를 수정했다.

코드

package com.algo.boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ2667Numbering {
	static class Node{
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}

	}

	private static int[][] map;
	private static int N, mini , minj;
	private static boolean[][] visited;
	private static int[] dx= {1,-1,0,0};
	private static int[] dy= {0,0,1,-1};
	private static ArrayList<Integer> rank;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = line.charAt(j)-'0';
			}
		}
		visited = new boolean[N][N];
		rank = new ArrayList<>();
		bfs();
		sb.append(rank.size()).append("\n");
		Collections.sort(rank);
		for (int val: rank) {
			sb.append(val).append("\n");
		}
		System.out.print(sb);
		br.close();
	}

	private static void bfs() {
		Queue<Node> q = new LinkedList<>();
		Node s = selectOne(mini, minj);
		int cnt = 0;
		while(s!=null) {
			q.offer(s);
			visited[s.x][s.y]=true;
			map[s.x][s.y]=0;
			cnt= 1;
			while (!q.isEmpty()) {
				int size = q.size();
				for (int i = 0; i < size; i++) {
					Node n = q.poll();
					for (int d = 0; d < 4; d++) {
						int nx =n.x+dx[d];
						int ny =n.y+dy[d];
						if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
						if(visited[nx][ny]) continue;
						if(map[nx][ny]==0)continue;
						map[nx][ny]=0;
						visited[nx][ny]=true;
						q.offer(new Node(nx,ny));
						cnt++;
					}
				}
			}
			rank.add(cnt);
			s = selectOne(mini, minj);
		}
	}

	private static Node selectOne(int x, int y) {
		int c=0;
		for (int i = x; i < N; i++) {
			if(i==x) {
				c =y;
			}else
				c=0;
			for (int j = c; j < N; j++) {

				if(map[i][j]==1) {
					mini = i;
					minj = j;
					return new Node(i,j);
				}
			}
		}
		return null;
	}

}
package com.algo.boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

public class BOJ2667Numbering {
	static class Node{
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	private static int[][] map;
	private static int N, mini , minj;
	private static int[] dx= {1,-1,0,0};
	private static int[] dy= {0,0,1,-1};
	private static ArrayList<Integer> rank;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = line.charAt(j)-'0';
			}
		}
		rank = new ArrayList<>();
		bfs();
		sb.append(rank.size()).append("\n");
		Collections.sort(rank);
		for (int val: rank) {
			sb.append(val).append("\n");
		}
		System.out.print(sb);
		br.close();
	}

	private static void bfs() {
		LinkedList<Node> q = new LinkedList<>();
		Node s = selectOne(mini, minj);
		int cnt = 0;
		while(s!=null) {
			q.offer(s);
			map[s.x][s.y]=0;
			cnt= 1;
			while (!q.isEmpty()) {
				int size = q.size();
				for (int i = 0; i < size; i++) {
					Node n = q.poll();
					for (int d = 0; d < 4; d++) {
						int nx =n.x+dx[d];
						int ny =n.y+dy[d];
						if(nx<0 || ny<0 || nx>=N || ny>=N || map[nx][ny]==0) continue;
						cnt++;
						map[nx][ny]=0;
						q.offer(new Node(nx,ny));
					}
				}
			}
			rank.add(cnt);
			s = selectOne(mini, minj);
		}
	}

	private static Node selectOne(int x, int y) {
		int c=0;
		for (int i = x; i < N; i++) {
			if(i==x) {
				c =y;
			}else
				c=0;
			for (int j = c; j < N; j++) {
				if(map[i][j]==1) {
					mini = i;
					minj = j;
					return new Node(i,j);
				}
			}
		}
		return null;
	}

}

Related Posts

답글 남기기

이메일 주소는 공개되지 않습니다.

%d 블로거가 이것을 좋아합니다: