알고리즘/BOJ - Java
[BOJ/Java] 15649. N과 M (1)
ImJay
2024. 2. 4. 16:05
반응형
[BOJ/Java] 15649. N과 M (1)
16918번: 봄버맨
첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.
www.acmicpc.net
풀이
package edu.ssafy.im.BOJ.No15649;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
int[] arr; // 주어진 자연수 배열
int[] sel; // 선택한 숫자들을 담을 배열
boolean[] visited; // 방문 여부를 체크할 배열
StringBuilder sb = new StringBuilder(); // 결과를 담을 StringBuilder
public static void main(String[] args) throws IOException {
new Main().sol();
}
private void sol() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력 처리
String input = br.readLine();
StringTokenizer st = new StringTokenizer(input);
int n = Integer.parseInt(st.nextToken()); // 주어진 자연수의 개수
int m = Integer.parseInt(st.nextToken()); // 선택할 숫자의 개수
arr = new int[n]; // 주어진 자연수 배열 초기화
sel = new int[m]; // 선택한 숫자 배열 초기화
visited = new boolean[n]; // 방문 여부 배열 초기화
// 주어진 자연수 배열 초기화
for (int i = 1; i <= arr.length; i++) {
arr[i - 1] = i;
}
recursive(0); // 재귀 함수 호출하여 수열 생성
System.out.print(sb); // 결과 출력
}
private void recursive(int m) {
// 기본 파트: 선택할 숫자의 개수만큼 숫자를 선택한 경우
if (m == sel.length) {
for (int s : sel)
sb.append(s).append(" "); // 선택한 숫자들을 StringBuilder에 추가
sb.append("\n"); // 줄바꿈
return;
}
// 재귀 파트
for (int i = 0; i < arr.length; i++) {
if (!visited[i]) { // 아직 방문하지 않은 숫자인 경우
visited[i] = true; // 방문 표시
sel[m] = arr[i]; // 선택한 숫자 배열에 추가
recursive(m + 1); // 다음 위치로 이동하여 재귀 호출
visited[i] = false; // 방문 표시 해제 (백트래킹)
}
}
}
}
반응형