Jam's story
[백준] 2667번 단지번호붙이기 다시풀어보기 (DFS, BFS)- JAVA 본문
📌입력값에 띄어쓰기가 없기때문에 StringTokenizer가 아닌 charAt 사용하기
📌한줄입력받은 String input에
int형 변수= input.charAt(j)-' 0'
Integer.parseInt(input.charAt(j)+"")
dfs 사용
package days01;
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.Collections;
import java.util.Iterator;
public class B2667 {
static int area[][];
static int N=0, count=0;
static int[] moveX= {-1,0,1,0};
static int[] moveY= {0,1,0,-1};
static ArrayList<Integer> list;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
N=Integer.parseInt(br.readLine());
area=new int[N][N];
for (int i = 0; i < N; i++) {
String input=br.readLine();
for (int j = 0; j <N; j++) {
area[i][j]=input.charAt(j)-'0';
//area[i][j]=Integer.parseInt(input.charAt(j)+"");
}
}//for-i
count=0;
list=new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(area[i][j]==1) {
count=1;
dfs(i,j);
list.add(count);
}
}
}//for-i
Collections.sort(list); //오름차순 정렬
System.out.println(list.size());
Iterator<Integer> ir =list.iterator();
while(ir.hasNext()) {
System.out.println(ir.next());
}
}
public static int dfs(int i, int j) {
area[i][j]=0;
for (int k = 0; k < 4; k++) {
int nx=i+moveX[k];
int ny=j+moveY[k];
if(nx>=0 && nx<N && ny >=0 && ny<N) {
if(area[nx][ny]==1 ) {
count++;
dfs(nx,ny);
}
}//if
}//for-k
return count;
}
}
bfs 사용
package days01;
import java.awt.Point;
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.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
public class B2667 {
static int area[][];
static int N=0, count=0;
static int[] moveX= {-1,0,1,0};
static int[] moveY= {0,1,0,-1};
static ArrayList<Integer> list;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
N=Integer.parseInt(br.readLine());
area=new int[N][N];
for (int i = 0; i < N; i++) {
String input=br.readLine();
for (int j = 0; j <N; j++) {
area[i][j]=input.charAt(j)-'0';
//area[i][j]=Integer.parseInt(input.charAt(j)+"");
}
}//for-i
count=0;
list=new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(area[i][j]==1) {
count=1;
bfs(i,j);
list.add(count);
}
}
}//for-i
Collections.sort(list); //오름차순 정렬
System.out.println(list.size());
Iterator<Integer> ir =list.iterator();
while(ir.hasNext()) {
System.out.println(ir.next());
}
}
public static int bfs(int i, int j) {
area[i][j]=0;
Queue<Point> que=new LinkedList<Point>();
que.add(new Point(i,j));
while(!que.isEmpty()) {
Point p=que.poll();
for (int k = 0; k < 4; k++) {
int nx=p.x+moveX[k];
int ny=p.y+moveY[k];
if(nx>=0 && nx<N && ny >=0 && ny<N) {
if(area[nx][ny]==1 ) {
que.add(new Point(nx,ny));
area[nx][ny]=0;
count++;
}
}//if
}//for-k
}//while
return count;
}
}7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
0,1:count :1
0,2:count :2
1,1:count :3
1,2:count :4
2,1:count :5
2,2:count :6
2,0:count :7
0,4:count :1
1,4:count :2
2,4:count :3
3,4:count :4
3,5:count :5
3,6:count :6
2,6:count :7
1,6:count :8
4,1:count :1
5,1:count :2
5,2:count :3
6,1:count :4
5,3:count :5
6,2:count :6
5,4:count :7
6,3:count :8
5,5:count :9
3
7
8
9
다른사람풀이
dfs
package 그래프탐색;
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class B2667 {
static int n,count;
static int[] dx = {-1,0,1,0};
static int[] dy = {0,-1,0,1};
static int[][] arr;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuffer sb = new StringBuffer();
List<Integer> answerList = new ArrayList<>();
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
visited = new boolean[n][n];
for(int i = 0; i< n; i++){
String input = br.readLine();
for(int j = 0; j< n; j++){
arr[i][j] = Integer.parseInt(String.valueOf(input.charAt(j)));
}
}
for(int i = 0; i< n; i++){
for(int j = 0; j< n; j++){
if(arr[i][j] == 1 && !visited[i][j]){
count = 1;
System.out.println(i+","+j+": count="+count);
answerList.add(dfs(i,j));
}
}
}
Collections.sort(answerList);
sb.append(answerList.size()).append("\n");
for(Integer i : answerList){
sb.append(i).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
private static int dfs(int x, int y){
visited[x][y] = true;
for(int i = 0; i< 4; i++){
int nextX = x + dx[i];
int nextY = y + dy[i];
if(nextX >= 0 && nextY >= 0 && nextX < n && nextY < n){
if(!visited[nextX][nextY] && arr[nextX][nextY] == 1){
System.out.println(nextX+","+nextY);
dfs(nextX,nextY);
count += 1;
System.out.println(nextX+","+nextY+": count="+count);
}
}
}
return count;
}
}7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
0,1: count=1
1,1
2,1
2,0
2,0: count=2
2,2
1,2
0,2
0,2: count=3
1,2: count=4
2,2: count=5
2,1: count=6
1,1: count=7
0,4: count=1
1,4
2,4
3,4
3,5
3,6
2,6
1,6
1,6: count=2
2,6: count=3
3,6: count=4
3,5: count=5
3,4: count=6
2,4: count=7
1,4: count=8
4,1: count=1
5,1
6,1
6,2
5,2
5,3
6,3
6,3: count=2
5,4
5,5
5,5: count=3
5,4: count=4
5,3: count=5
5,2: count=6
6,2: count=7
6,1: count=8
5,1: count=9
3
7
8
9
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] DFS와 BFS - java (0) | 2022.08.10 |
|---|---|
| [백준] 1325번 효율적인 해킹 dfs- java (0) | 2022.08.09 |
| [백준] 나이트의 이동 다시 풀어보기 (BFS) - JAVA (0) | 2022.08.07 |
| [백준] 2667번 단지번호 붙이기 - java (0) | 2022.08.05 |
| [백준] 7562번 나이트의 이동 - java (0) | 2022.08.04 |
'코딩테스트/백준' Related Articles
more
Comments