반응형
백준 DFS 문제
#2667 - 단지번호붙이기
https://www.acmicpc.net/problem/2667
사용한 개념
1) DFS
저는 깊이탐색을 사용했습니다.
우선, 2차원 배열에서 0이 아닌 1인 경우에 깊이탐색을 시작하여 인접해있는 1을 모두 찾게합니다. 그 다음 다시 탐색을 이어가 0이 아닌 1인경우 다시 깊이탐색을 시작합니다. 여기서 달라지는 점은, 이미 탐색을 했다라는 표시를 하기 위해 임시 변수 값이 CNT의 값을 증가시켜 해당 값으로 매핑시켜 표시합니ㅁ다.
따라서..
1 1 0 0 0
1 0 0 0 0
0 0 0 1 1
1 1 0 1 1
0 1 0 0 1
인 경우,
2 2 0 0 0
2 0 0 0 0
0 0 0 3 3
4 4 0 3 3
0 4 0 0 3
위와 같이 매핑되는 것입니다.
그 다음, 매핑된 2이상의 숫자들을 숫자별로 카운트 해주면 됩니다.
cnt 는 현재 단지그룹의 수라고 보시면 됩니다.
그만큼 1차원 배열을 생성해주고, 자신이 소속된 단지번호의 값을 증가시켜 자연스럽게 1차원 배열의 index가 해당 단지 번호가 되고 그안에 있는 값은 단지번호 수가 되는 것입니다.
count = new int[cnt]; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(map[i][j] > 1){ count[map[i][j]-2]++; } } }
그렇게 어려운 문제는 아닙니다. 다만, 처음 DFS를 접근한다면 재귀호출에 대해 익숙해질 필요가 있습니다.
static int[] goX = {-1, 0, 1, 0}; static int[] goY = {0, 1, 0, -1}; private static void DFS(int a, int b, int k) { map[a][b] = k; for(int i=0; i<4; i++){ int dx = a + goX[i]; int dy = b + goY[i]; if((-1< dx && dx<n) && (-1< dy && dy<n) && map[dx][dy] == 1){ DFS(dx, dy, k); } } }
아래는 전체소스 입니다. 궁굼하신 점은 댓글에 남겨주세요.
package BackJoon.DFS; import java.util.Arrays; import java.util.Scanner; public class PostingNumber { static int[][] map; static int[] count; static int n = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); map = new int[n][n]; for(int i=0; i<n; i++){ String str = sc.next(); for(int j=0; j<n; j++){ map[i][j] = Integer.parseInt(str.charAt(j)+""); } } solution(); System.out.println(cnt); Arrays.sort(count); for(int i=0; i<count.length; i++){ if(count[i] != 0) System.out.println(count[i]); } } static int cnt = 1; private static void solution() { for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(map[i][j] == 1){ DFS(i,j,++cnt); } } } count = new int[cnt]; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(map[i][j] > 1){ count[map[i][j]-2]++; } } } } static int[] goX = {-1, 0, 1, 0}; static int[] goY = {0, 1, 0, -1}; private static void DFS(int a, int b, int k) { map[a][b] = k; for(int i=0; i<4; i++){ int dx = a + goX[i]; int dy = b + goY[i]; if((-1< dx && dx<n) && (-1< dy && dy<n) && map[dx][dy] == 1){ DFS(dx, dy, k); } } } }
반응형
'Algorithm > BackJoon' 카테고리의 다른 글
[BackJoon] 백준 1697 숨바꼭질(BFS) (0) | 2019.01.03 |
---|---|
[BackJoon] 백준 2606 바이러스(DFS) (0) | 2018.12.11 |
[삼성SW테스트] 사다리 조작 15684(백준) (0) | 2018.07.07 |
[삼성SW테스트] 드래곤 커브 15685(백준) (3) | 2018.06.23 |
[삼성SW테스트] 치킨배달 15686(백준) (0) | 2018.06.16 |
댓글