오늘의 코테 문제
오늘의 코테 문제는 도미노? 이다.
문제 자체의 해석은 어렵지 않았다.
private static void dfs(int k) {
if (k == m) {
//사이클을 판별
int sum=0;
for(int i=0; i<m; i++){
sum *= arr[i].value;
System.out.print(arr[i].x + " : "+arr[i].y+ " | ");
} System.out.println();
findCycle();
return;
}
int ist = 1;
int tst = 1;
//그 다음 선택지를 사용
if (k != 0) {
Pos cur = arr[k - 1];
ist = cur.x;
tst = cur.y;
} for (int i = ist; i <= m; i++) {
for (int t = tst; t <= m; t++) {
if (col[i] < 2) {//행 2회 이만
if (row[t] < 2 && isused[i][t] == 0) {// 열 2 회선택 미만인 경우에만
//map의 위저 정보 값 넣어주기
//뽑은 값은 배제를 위해서 배제하는 배열 만들기
col[i] = col[i] + 1;
row[t] = row[t] + 1;
isused[i][t] = 1;
arr[k] = new Pos(i, t, map[i][t]);
dfs(k + 1);//하고 들어가서 또 탐색
col[i] = col[i] - 1;
row[t] = row[t] - 1;
isused[i][t] = 0;
} } } } }
개인적으로는 완전탐색에서 내가 원하고싶은 데이터만 뽑는게 조금 재미있었다(?) N과 M문제를 풀면서 알게된 조합을 기본 틀로 사용했고 2차원 배열의 데이터를 정렬해서 뽑는건 이번이 처음이었기 때문
재귀함수를 이용한 탐색의 특징
끝나는 지점이 명확함
if (k == m) {
//사이클을 판별
int sum=0;
for(int i=0; i<m; i++){
sum *= arr[i].value;
System.out.print(arr[i].x + " : "+arr[i].y+ " | ");
} System.out.println();
findCycle();
return;
} 여기서 k는 depth이고 m은 깊이? 내가 도달하고싶은 깊이이다. k==m이 되는 순간 코드는 종료된다. 여기서 m이 직접적으로 의미하는것은 조합의 수이다. 내가 만약에 조합을 했을 때 그 결과 3종류로 이루어진 애들이었으면 좋겠다? 그럴때 종료의 조건이 depth가3이 된 경우이다.
재귀 함수를 돌리기 위해 필요한 준비물
static int m; //노드의 수
static int[][] map; //map의 정보 탐색하려는 것의 정보
//자기자신 제외 중복
static int[][] isused; //썻는지 안썼는지 표시할 것
// 문제에서 같은 행에서 2개 초과로 뽑아쓰면 안된다고 했으니까 그걸 확인해줄 애들
static int[] col;
//마찬가지로 같은 열에서 2개 초과로 뽑아쓰면 안된다고 헀으니까 그걸 확인할 애들
static int[] row;
//위치값을 저장할 배열
static Pos[] arr;이렇게 전역변수에 지정해놓고
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());//depth가 된다.
m = tc;
col = new int[tc+10];
row = new int[tc+10];
map = new int[tc + 10][tc + 10]; // 0,0라인 배제를 위해서
isused = new int[tc + 10][tc + 10];
arr = new Pos[m];
mVis = new int[m+1];재귀가 시작되기 전에 값을 초기화 해준다.
문제에서 바라는 조건에 맞춰 코드 짜기
//시작점 위치 조절
// for문의 시작점 위치 조절은 순열의 중복을 제거한다.
// ex) 1,1 | 2,1 -> 2,1 | 1,1 -> 둘은 같다고 판단해서 이걸 제거해주는 역할
//depth가 0일때는 ist는 초기값으로 들어간다.
int ist = 1;
int tst = 1;
//depth가 0이 아니게 될때에는 arr배열에 k-1(그 전 depth에서 저장한 값)을 넣어준다.
if (k != 0) {
//그 전에 선택했던 것 이후부터 수행해야 하기 때문이다.
Pos cur = arr[k - 1];
ist = cur.x;
tst = cur.y;
//시작점을 ist,tst로 지정 이러면 순열의 중복을 제거할 수 있다.
} for (int i = ist; i <= m; i++) {
for (int t = tst; t <= m; t++) {
//어떤 행을 선택하는데 그 행에서 사용한 값이 2회 미만인 경우
if (col[i] < 2) {//행 2회 미만
//어떤 열을 선택하는데 그 열에서 사용한 값이 2회 미만인 경우
if (row[t] < 2 && isused[i][t] == 0) {// 열 2 회선택 미만인 경우에만
//map의 위저 정보 값 넣어주기
//뽑은 값은 배제를 위해서 배제하는 배열 만들기
//해당 열과 행에서 원소를 뽑았으니까 값에 표시해주기
//해당col[idx]값이 2 이상이된다면 쓸 수 없게 된다.
col[i] = col[i] + 1;
//해당 열에서도 값을 뽑았으니까 체크해주기
row[t] = row[t] + 1;
//좌표값을 사용했으니까 isused에 표시해주기
//isused의 사용 여부는 본인을 뽑는걸 막는다.
//ex) 1,1 | 1,1 -> 이 경우를 막아줌
isused[i][t] = 1;
//arr은 백트래킹의 값이 들어가게된다.
//Pos객체는 각 좌표의 정보와 , 좌표의 값을 저장함
arr[k] = new Pos(i, t, map[i][t]);
dfs(k + 1);//하고 들어가서 또 탐색
//백트래킹을 위해서 표시해놨던거 다 되돌려주기
col[i] = col[i] - 1;
row[t] = row[t] - 1;
isused[i][t] = 0;
} } } } } Pos는 x,y의 정보를 담고있다. 배열로넣기 싫어서 저렇게 넣었다. 아무튼
재귀의 시작점은 순열의 중복을 제거해준다
isused는 본인의 중복 사용을 제거해준다.(1,1 | 1,1의 조합 방지)
arr은 백트래킹의 값 혹은 index가 들어가게된다.
나는 위의 규칙을 따라서 백트래킹을 짜고있다. 그래서 딱히 짜는데 어렵다거나 하진 않았던 것 같다.
~~하지만 그래프는 못풀었죠?
아무튼
재귀로 푸는건 잘 풀었는데 또 그래프문제에서 막혔다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ다 풀어놓고 ㅠ
전체코드 (그래프 노드 탐색만 남았는데 그거 몬함)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main {
static int m; //노드의 수
static int[][] map;
//자기자신 제외 중복
static int[][] isused;
static int[] col;
static int[] row;
//위치값을 저장할 배열
static Pos[] arr;
// 방문 상태를 저장할 배열 (사이클 판별용)
static int[][] cycleInfo;
//지나간 노드인지 확인하는 배열
static int[] mVis;
//결과값 출력
static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;
private static class Pos {
int x, y, value;
public Pos(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
}
private static int findCycle(){
for(int i=0; i<m; i++){
for(int k=0; k<m; k++){
} }
return 0;
}
private static void dfs(int k) {
if (k == m) {
//사이클을 판별
int sum=0;
for(int i=0; i<m; i++){
sum *= arr[i].value;
System.out.print(arr[i].x + " : "+arr[i].y+ " | ");
}
System.out.println();
findCycle();
return;
}
int ist = 1;
int tst = 1;
//그 다음 선택지를 사용
if (k != 0) {
Pos cur = arr[k - 1];
ist = cur.x;
tst = cur.y;
}
for (int i = ist; i <= m; i++) {
for (int t = tst; t <= m; t++) {
if (col[i] < 2) {//행 2회 이만
if (row[t] < 2 && isused[i][t] == 0) {// 열 2 회선택 미만인 경우에만
//map의 위저 정보 값 넣어주기
//뽑은 값은 배제를 위해서 배제하는 배열 만들기
col[i] = col[i] + 1;
row[t] = row[t] + 1;
isused[i][t] = 1;
arr[k] = new Pos(i, t, map[i][t]);
dfs(k + 1);//하고 들어가서 또 탐색
col[i] = col[i] - 1;
row[t] = row[t] - 1;
isused[i][t] = 0;
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());//depth가 된다.
m = tc;
col = new int[tc+10];
row = new int[tc+10];
map = new int[tc + 10][tc + 10]; // 0,0라인 배제를 위해서
isused = new int[tc + 10][tc + 10];
arr = new Pos[m];
mVis = new int[m+1];
String temp = "";
for (int i = 1; i <= tc; i++) {
temp = br.readLine();
for (int k = 1; k <= tc; k++) {
if (temp.charAt(k - 1) >= 65 && temp.charAt(k - 1) <= 73) {
map[i][k] = (temp.charAt(k - 1) - 64) * -1;
} else {
map[i][k] = temp.charAt(k - 1) - '0';
}
}
}
// for(int i=1; i<=tc; i++){
// for(int k=1; k<=tc; k++){
// System.out.print(map[i][k]+ " ");
// }
// System.out.println();
// }
dfs(0);
System.out.println(max);
System.out.println(min);
}
}REVIEW
2차원 배열의 조합은 처음이라 신선했따. 그리고 나름 어렵지 않아서 조금 기뻣다. 그래프뺴고
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
Yellta가 BE개발해요! 왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜 가 제일 중요하죠