-
2667 단지번호 붙이기카테고리 없음 2021. 10. 27. 13:32
입력 받은 값을
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