[백준] S2 2210 숫자판 점프 (java)

www.acmicpc.net/problem/2210

2210번: 숫자판 점프

 

풀이

 

1) 이차원 배열을 탐색하면서 dfs를 돈다

2) dfs 6개뽑으면 set 에담는다 (중복제거용)

3) set의 크기 출력

 

주의사항

 

1) 없음

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class BJ_S2_2210_숫자판점프 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N = 5;
	static Set<String> set = new HashSet<>();
	static StringBuffer sb;
	static int map[][] = new int[N][N];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<N; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}	
		}
		
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				sb = new StringBuffer();
				sb.append(map[r][c]);
				dfs(r,c,0);
			}	
		}
		System.out.println(set.size());
	}

	private static void dfs(int r, int c, int depth) {
		if(depth == 5) {
			set.add(sb.toString());
			
			return;
		}
		for(int d=0; d<4; d++) {
			int nr = r+dr[d];
			int nc = c+dc[d];
			
			if(isIn(nr, nc)) {
				sb.append(map[nr][nc]);
				dfs(nr, nc, depth+1);
				sb.deleteCharAt(depth+1);
			}
		}
	}
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<N);
	}
	
	static int dr[] = {0,0,-1,1};
	static int dc[] = {-1,1,0,0};

	static String src =
			"1 1 1 1 1\r\n" + 
			"1 1 1 1 1\r\n" + 
			"1 1 1 1 1\r\n" + 
			"1 1 1 2 1\r\n" + 
			"1 1 1 1 1";
}

 

 

후기

 

실버2지만 dfs를 알면 브론즈보다 빨리 풀 수 있는 쉬운 문제였다.