티스토리 뷰
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, danjiCnt;
static int[][] graph = new int[26][26];
static int[] num = new int[26*26];
static boolean dfs (int x, int y) {
if (x < 1 || x > n || y < 1 || y > n) {
return false;
}
// 단지가 될 수 있다면
if (graph[x][y] == 1) {
graph[x][y] = 0;
num[danjiCnt]++;
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
return true;
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
// graph 입력
for (int i = 1; i <= n; i++) {
String str = br.readLine();
for (int j = 1; j <= n; j++) {
graph[i][j] = str.charAt(j-1) - '0';
}
}
// graph 순회하면서 dfs 실행
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dfs(i, j)) {
danjiCnt++;
}
}
}
// 출력
System.out.println(danjiCnt);
Arrays.sort(num);
for (int value : num) {
if (value != 0) {
System.out.println(value);
}
}
}
}
- 얼음 채우기에서 봤던 느낌이랑 비슷해서 DFS로 접근했다.
- 삽질하면서 시간도 많이쓰고 정답을 맞추긴했는데 버거웠따 ...
- 바로 넘어가지말고 다른 사람풀이를 봐서 생각 따라가는거 연습해보자
1. 사용 할 변수 선언
1-1) int n, danjiCnt / int[26][26] graph
int num[26*26] : 처음엔 num[26]이었고 런타임오류가 떠서 다시 코드를봤는데 26으로 하면 25x25로 가장 큰 배열일때
그 danjiCnt 가 26을 넘어버릴수도 있기에 크게 잡음. 약간 낭비일수도있는데 몇으로 잡아야 할지 생각이 안났다.
2. 입력받고 dfs 함수 생성
2-1) 상하좌우로 움직일건데 만약에 x, y가 graph의 범위를 넘을경우 false
2-2) 그래프 탐색부분이 1일경우에 거기서 부터 같은 단지를 전부 탐색하기 위해 상하좌우로 dfs 호출
2-3) 이미 방문한곳은 0으로 만들어주고 num[danjiCnt]++;을 해준다 -> 한 단지에 있는 아파트 수 카운팅
3. 메인함수에서 dfs 호출
3-1) 모든 배열에서 dfs를 돌아야하니까 이중 for문 사용
3-2) 만약에 dfs 함수가 true값을 반환하면 하나의 단지를 이뤘다는거니까 danjiCnt++;
4. 출력
4-1) 단지수 호출
4-2) 단지별 아파트를 오름차순으로 출력해야 하기에 Arrays.sort()로 오름차순 정렬후 0이 아닌 값을 출력
반응형
'PS > boj' 카테고리의 다른 글
boj)2178 - 미로 탐색 (0) | 2020.09.03 |
---|---|
boj)1012 - 유기농 배추 (0) | 2020.09.03 |
boj)2606 - 바이러스 (0) | 2020.09.03 |
boj)1260 - DFS와 BFS (0) | 2020.09.03 |
boj)18352 - 특정 거리의 도시 찾기 (0) | 2020.09.02 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- BOJ
- 모던자바스크립트
- 이펙티브자바 아이템60
- 이펙티브자바 스터디
- 김영한 http
- 킹수빈닷컴
- 백기선 스터디
- 이펙티브자바 아이템59
- REST API
- 프로그래머스
- HTTP 완벽가이드
- dreamcoding
- js array
- js api
- 이펙티브자바
- 패스트캠퍼스 컴퓨터공학 완주반
- GCP
- Spring Security
- HTTP 완벽 가이드
- 프로그래머스 SQL
- java
- http
- 백준
- js promise
- 드림코딩
- JS 딥다이브
- 집 구하기
- JPA 연관관계 매핑
- 김영한 JPA
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
글 보관함