2667 단지번호 붙이기
입력 받은 값을
stringTokenizer st = new StringTokenizer(br.readLine(), "");
이런식으로 분리해서 0,1,0,1 이런식으로 토큰 분리하려고 했는데
stringTokenizer는 이렇게 구분자 없이는 분리가 불가능? 한 듯 해서.....
그래서 map[i][j]= Integer.parseInt(String.valueOf(s.charAt(j)));
이렇게 해결
참고
[백준] 2667 : 단지번호붙이기 (JAVA/자바)
BOJ 2667 : 단지번호붙이기 - https://www.acmicpc.net/problem/2667모든 칸을 확인하는데, 집이 있으나 단지 번호가 아직 부여되지 않은 경우(==값은 1이고 visited되지 않은 경우) BFS탐색으로 인접한 집들에 단
velog.io
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class position{
int x;
int y;
position(int x, int y) {
this.x = x;
this.y= y;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int map [][]= new int [N][N];
for(int i= 0; i<N;i++) {
String s = br.readLine();
for(int j=0; j<N;j++) {
map[i][j]= Integer.parseInt(String.valueOf(s.charAt(j)));
}
}
boolean visit[][]= new boolean [N][N];
StringBuilder sb = new StringBuilder();
for(int i= 0; i<N;i++) {
for(int j=0; j<N;j++) {
if(map[i][j]==1 && !visit[i][j]) {
int count = dfs(i,j,N,map,visit);
sb.append(count);
}
}
}
String result[] = sb.toString().split("");
Arrays.sort(result);
System.out.println(result.length);
for(String a : result) {
System.out.println(a);
}
}
public static int dfs(int i, int j,int N, int map[][],boolean visit[][]) {
Queue<position> queue = new LinkedList<>();
queue.add(new position(i,j));
visit[i][j]=true;
int count =1;
while(!queue.isEmpty()) {
position a = queue.remove();
int dx[]= {-1,1,0,0};
int dy[]= {0,0,-1,1};
for(int k=0; k<4;k++) {
int x = a.x+dx[k];
int y = a.y+dy[k];
if(x>=0 && y>=0 && x<N && y<N ) {
if(!visit[x][y]&&map[x][y]==1) {
queue.add(new position(x,y));
visit[x][y]=true;
count++;
}
}
}
}
return count;
}
}
이렇게 구현하니 뭔가 sts ide에서는 잘돌아가는데, 백준에 정답제출하니 틀렸다고 했다.
왜 그러나 생각해보니, dfs는 큐가 아니라 스택이나 재귀함수로 구현한다 ㅠ
기본적인 것을 생각하지 않고 코드를 짜서 실패했다.
그래서 스택이나 재귀로 다시 구현
<최종 완성본>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int map [][]= new int [N][N];
for(int i= 0; i<N;i++) {
String s = br.readLine();
for(int j=0; j<N;j++) {
map[i][j]= Integer.parseInt(String.valueOf(s.charAt(j)));
}
}
boolean visit[][]= new boolean [N][N];
ArrayList<Integer> result = new ArrayList<>();
for(int i= 0; i<N;i++) {
for(int j=0; j<N;j++) {
if(map[i][j]==1 && !visit[i][j]) {
count = 1;
dfs(i,j,N,map,visit);
result.add(count);
}
}
}
Collections.sort(result);
System.out.println(result.size());
for(int a : result) {
System.out.println(a);
}
}
public static int dfs(int i, int j,int N, int map[][],boolean visit[][]) {
visit[i][j]=true;
int dx[]= {-1,1,0,0};
int dy[]= {0,0,-1,1};
for(int k=0; k<4;k++) {
int x = i+dx[k];
int y = j+dy[k];
if(x>=0 && y>=0 && x<N && y<N ) {
if(!visit[x][y]&&map[x][y]==1) {
dfs(x,y,N,map,visit);
count++;
}
}
}
return count;
}
}
주의할점 :
1)
원래는 StringBuilder를 사용해서 count값을 출력하려고 했었다.
즉
StringBuilder sb = new StringBuilder();
for(int i= 0; i<N;i++) {
for(int j=0; j<N;j++) {
if(map[i][j]==1 && !visit[i][j]) {
count = 1;
dfs(i,j,N,map,visit);
sb.append(count);
}
}
}
String result [] = sb.toString().split("");
Arrays.sort(result);
System.out.println(result.length);
for(String a : result) {
System.out.println(a);
}
}
이렇게 arraylist를 사용하지 않고 StringBuilder로 dfs 한 후의 count값을 받아서 그 결과를 출력하려고 했는데,
이 경우 String을 Arrays.sort하는데,
여기서 count값들은 7,8,9로 String이 아니라 int값이라 그런지
백준에 제출했을 때 오류가 났다.
그래서 참고자료를 참고해서 저렇게 ArrayList로 받으니깐 정답을 만들 수 있었다.
2)
그리고 count를 static 변수로 하지 않고, dfs(count)를 집어넣어서 main 메소드에서 dfs 메소드로 전달해주려고 했다.
그런데 결과값이 이상하게 나왔다.
즉
int count;
for(int i= 0; i<N;i++) {
for(int j=0; j<N;j++) {
if(map[i][j]==1 && !visit[i][j]) {
count = 1;
count = dfs(i,j,N,map,visit,count);
result.add(count);
}
}
}
Collections.sort(result);
System.out.println(result.size());
for(int a : result) {
System.out.println(a);
}
}
public static int dfs(int i, int j,int N, int map[][],boolean visit[][],int count) {
visit[i][j]=true;
int dx[]= {-1,1,0,0};
int dy[]= {0,0,-1,1};
for(int k=0; k<4;k++) {
int x = i+dx[k];
int y = j+dy[k];
if(x>=0 && y>=0 && x<N && y<N ) {
if(!visit[x][y]&&map[x][y]==1) {
count++;
dfs(x,y,N,map,visit,count);
}
}
}
return count;
}
}
이렇게 dfs에다가 count변수를 넘겨주는 거로 했더니
결과가
이렇게 2 2 2 가 나왔다.
그래서 System.out.println()을 사용해서 count값을 찍어봤더니
public static int dfs(int i, int j,int N, int map[][],boolean visit[][],int count) {
***********************
System.out.println(count);
***********************
visit[i][j]=true;
int dx[]= {-1,1,0,0};
int dy[]= {0,0,-1,1};
for(int k=0; k<4;k++) {
int x = i+dx[k];
int y = j+dy[k];
if(x>=0 && y>=0 && x<N && y<N ) {
if(!visit[x][y]&&map[x][y]==1) {
count++;
dfs(x,y,N,map,visit,count);
}
}
}
return count;
1
2
3
4
5
6
7
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
9
3
2
2
2
이렇게 결과값이 나왔다
뭔가 7 8 9 가 나오긴 하는 것 같은데 얘네가 어디로 가는건지,
public static int dfs(int i, int j,int N, int map[][],boolean visit[][],int count) {
System.out.println(count);
visit[i][j]=true;
int dx[]= {-1,1,0,0};
int dy[]= {0,0,-1,1};
for(int k=0; k<4;k++) {
int x = i+dx[k];
int y = j+dy[k];
if(x>=0 && y>=0 && x<N && y<N ) {
if(!visit[x][y]&&map[x][y]==1) {
count++;
dfs(x,y,N,map,visit,count);
}
}
}
*****************************
System.out.println("언제");
**************************
return count;
그래서 이렇게 count값을 return언제하나 확인해보려고 "언제" 라는 글자를 출력해보았더니
1
2
3
4
언제
5
6
7
언제
언제
언제
언제
언제
언제
1
2
3
4
5
6
7
8
언제
언제
언제
언제
언제
언제
언제
언제
1
2
3
4
5
6
7
언제
8
9
언제
언제
언제
언제
언제
언제
언제
언제
3
2
2
2
이렇게 결과값이 나왔다.
dfs가 아무래도 4가지 방향으로 계속 확인하다보니, 이런 결과가 나온 것 같은데,
아직 내가 실력 부족인 듯 하여,
다음 번에 더 알아보도록 하겠다.
참고 자료 :
[백준 알고리즘] 백준 2667번 단지번호붙이기 자바(Java)
츄르사려고 코딩하는 코집사입니다. 1. [백준 알고리즘] 백준 2667번 단지번호붙이기 자바(Java) 1) 문제번호 : 2667번 2) 문제 출처 www.acmicpc.net/problem/2667 과 같이 정사각형 모양의 지도가 있다. 1..
yongku.tistory.com