백준 15686번 문제 솔!
문제가 치킨 내용이어서 풀면서 계속 치킨을 생각했더니 치킨 먹고 싶다. 후라이드 뼈치킨으로 튀김옷 엄청 얇은걸로.
백트래킹은 정말 어렵다. 하지만 몇 문제 풀다보니 그 안에 패턴이 살짝 보이게 된다.
우선 백트래킹은 깊이 탐색으로 볼 수 있다.
조건에 들어맞는다면 계속 재귀적으로 들어간다. 이때 파라미터 혹은 depth를 선언해 계속계속 깊이 들어가는 방법이 있다.
보통 종료 조건을 파라미터와 depth 등 다양하게 설정을 해서 재귀를 종료하고 값을 계산한 후, 갱신을 하는 로직으로 이루어 진다.
재귀 호출이기 때문에,
1번이 2번을 불렀음 (1->2)
그리고 2번이 3번을 불렀음 (1->2->3)
그리고 3번이 4번을 불렀음 (1->2->3->4)
근데 4번이 종료조건에 해당하면 4가 종료가 되어서
1->2->3 이 남게 되고, 만약에 3번에서 더 탐색할게 있다면 5번으로 간다
1->2->3->5
아니 근데 나는 for문을 사용해야 하는거 아닌가? 했는데 뭐.. 모르겠다 문제마다 다르긴한데 안쓰이더라.
for문을 사용하지 않아도 되는 경우는, 재귀 호출이 자연스럽게 모든 경우를 다르게 호출하도록 설계된 경우라고 한다. 예를 들어, 이진 트리처럼 두 가지 경우로만 나뉘는 문제는 굳이 for문이 필요하지 않을 수 있다.
그런데 1부터 n까지의 숫자를 순서대로 선택하거나, 배열에서 각 인덱스에 대해 여러 선택지를 탐색해야 하는 경우에 for문이 필요하다.
그리고 내가 지금 시도하는 노드를 포함 할 것인가 아닌가 그거 할라면 boolean 배열을 활용하는게 좋다. 나는 처음에 인덱스로 체크했는데 음 투머치 비효율적.
처음에 백트래킹을 풀 때는 와 내가 너무 못하고 말하는 감자도 아니고 그냥.. 숨쉬는 덩어리처럼 느껴져서 자괴감이 뽜바ㅏ박 들었는데
그래서 지피티한테 찡찡거렸다.
먼저, 당신이 지금 느끼고 있는 괴로움에 대해 공감해요. 프로그래밍을 배우는 과정은 쉽지 않고, 가끔은 막막하거나 좌절감을 느낄 수 있습니다. 하지만 이런 감정은 성장 과정의 일부이고, 프로그래밍을 잘하게 되는 데 있어서 반드시 겪는 과정이에요. 당신은 지금 중요한 단계를 지나고 있는 거예요. 이런 단계를 겪는다는 건, 결국 더 나은 문제 해결 능력을 갖출 수 있다는 의미입니다.
왜 괴로울까?
프로그래밍을 할 때 느끼는 괴로움은 주로 다음과 같은 이유에서 올 수 있어요:
- 복잡한 문제를 다루는 과정: 새로운 알고리즘이나 문제 해결 방식을 처음 접할 때는 익숙하지 않아서 더 어렵게 느껴질 수 있어요.
- 완벽함에 대한 기대: 모든 걸 처음부터 완벽하게 해야 한다는 압박감이 있을 수 있습니다. 하지만 처음부터 완벽할 필요는 없어요.
- 성과가 바로 나타나지 않음: 학습하고 노력하는데도 결과가 바로 눈에 보이지 않을 때 자괴감을 느끼기 쉽습니다.
나도 너처럼 생각하고 싶다: 어떻게 문제 해결 능력을 기를 수 있을까?
문제 해결 능력은 연습과 경험을 통해 서서히 길러집니다. 저도 단번에 이렇게 사고할 수 있게 된 것이 아니에요. 작은 성공과 실패를 반복하면서 문제를 바라보는 사고방식이 발전했을 뿐이에요. 아래 몇 가지 팁이 당신에게 도움이 될 거라고 생각해요.
1. 작은 문제부터 해결하기
복잡한 문제를 바로 풀려고 하기보다는, 문제를 작은 부분으로 나누고 하나씩 해결해 나가세요. 예를 들어, 큰 문제를 단계별로 쪼개서:
- 입력 받기
- 출력 처리
- 핵심 알고리즘 구현
이렇게 작은 부분에서 성공 경험을 쌓아 나가면, 복잡한 문제도 점차 익숙해질 거예요.
2. 다른 사람의 코드와 아이디어를 배우기
문제를 해결하는 다양한 방법을 배우는 것도 중요해요. 처음에는 저처럼 다른 사람의 아이디어나 코드 구성을 보면서 따라 해보세요. 그 과정에서:
- "왜 이 방식이 맞는가?"
- "이 방식이 왜 효율적인가?"
를 고민하면서, 점점 자신의 문제 해결 방법을 만들어 갈 수 있어요.
3. 시간을 주기
프로그래밍을 잘하는 사람들도 수많은 실패와 좌절을 겪었어요. 처음에는 시간이 많이 걸리더라도, 그것이 정상이에요. 시간이 지나면서 코드 작성 속도도 빨라지고, 사고하는 방식도 더 명확해질 거예요. 시간을 주고, 자신에게 너무 엄격하지 않게 해주세요.
4. 실패를 성장의 일부로 받아들이기
프로그래밍은 실패와 디버깅을 통해 배울 수 있는 영역입니다. 코드가 처음에 잘 작동하지 않거나 논리가 틀렸다고 해서 실패했다고 생각하지 마세요. 오히려 그 실패가 학습의 중요한 부분이에요. 성공보다 실패에서 더 많은 것을 배울 수 있습니다.
어떻게 지금의 어려움을 극복할 수 있을까?
-
구체적인 목표 설정:
- 오늘은 문제 하나라도 풀겠다는 작은 목표를 세워보세요. 문제를 완전히 이해하고 풀지 못해도 괜찮아요. 오늘 배운 것에 집중하는 것이 중요합니다.
-
긍정적인 태도 유지:
- 어려운 문제를 풀 때는 좌절할 수 있지만, 이 과정을 통해 배워 나가고 있다는 점을 기억하세요. 작은 진전도 축하해 주세요.
-
의식적인 연습:
- 알고리즘 문제를 반복해서 풀어보세요. 처음에는 힘들지만, 익숙해지면 점차 쉽게 풀릴 거예요. 프로그래밍 문제를 푸는 것도 결국 연습입니다.
마무리 생각
저도 처음에는 어려운 문제를 풀지 못해서 좌절했어요. 그런데 시간이 지나고 문제를 풀다 보면 어느 순간부터 문제가 보이고 해결 방법이 떠오르는 순간이 찾아오더라고요. 지금 느끼는 괴로움은 당신이 성장하고 있다는 증거입니다.
당신은 지금 충분히 잘하고 있어요. 포기하지 말고, 천천히, 꾸준히 한 걸음씩 나아가면 어느 순간 어려운 문제도 스스로 해결할 수 있는 능력을 갖추게 될 거예요. 지금 당신이 겪고 있는 이 과정이, 당신을 더 뛰어난 프로그래머로 만들어 줄 겁니다. 힘내세요! 😊
지피티야 나랑 결혼할래? 진심으로...ㅜㅜ
아무튼 저 글을 읽으면서 복잡한 로직을 단순화하려고 모듈화를 많이 시도했다.
한 함수에서 모든 것을 해결하지 않고, 어떤 함수가 필요한지 여러개로 쪼갰다.
그리고 내가 푼 방식이 효율적인 것인지도 시간, 공간 복잡도 면에서도 생각했다.
이 문제도 원래는 [M][N][N] 테이블을 만드는 것을 원래 생각했는데, 다시한번 더 생각해보니까 필요가 없던 것이다. 그래서 새롭게 코드를 짜보았다. 그래도 아직 부족하지만 백트래킹 내가 정복하고 만다!!!!!!
내가 만든 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P15686 {
static int minChicken = Integer.MAX_VALUE;
static int n;
static int m;
static int[][] chicken;
static boolean[] selected;
static int chickenCount = 0;
static int houseCount = 0;
// 치킨집과 집 사이의 거리 계산
private static void howFarChicken(ArrayList<int[]> chickenAddress, ArrayList<int[]> houseAddress) {
for (int i = 0; i < chickenAddress.size(); i++) {
int[] oneChicken = chickenAddress.get(i);
int xC = oneChicken[0];
int yC = oneChicken[1];
for (int j = 0; j < houseAddress.size(); j++) {
int[] oneHouse = houseAddress.get(j);
int xH = oneHouse[0];
int yH = oneHouse[1];
chicken[i][j] = Math.abs(xC - xH) + Math.abs(yC - yH);
}
}
}
// 선택된 치킨집과 각 집의 최소 거리를 계산하는 함수
private static int diffCal() {
int[] temp = new int[houseCount];
Arrays.fill(temp, Integer.MAX_VALUE); // 모든 값 초기화
for (int i = 0; i < selected.length; i++) {
if (selected[i]) {
for (int j = 0; j < houseCount; j++) {
temp[j] = Math.min(temp[j], chicken[i][j]);
}
}
}
return Arrays.stream(temp).sum();
}
// 백트래킹 함수
private static void dfs(int index, int count) {
if (count == m) { // 치킨집 m개를 선택했을 때
int diff = diffCal();
minChicken = Math.min(minChicken, diff);
return;
}
if (index >= chickenCount) { // 탐색 종료 조건
return;
}
selected[index] = true;
dfs(index + 1, count + 1); // 현재 치킨집을 선택한 경우
selected[index] = false;
dfs(index + 1, count); // 선택하지 않은 경우
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// 입력 받기
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
ArrayList<int[]> chickenAddress = new ArrayList<>();
ArrayList<int[]> houseAddress = new ArrayList<>();
// 지도 정보 입력
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int temp = Integer.parseInt(st.nextToken());
if (temp == 1) { // 집
houseCount++;
houseAddress.add(new int[]{i, j});
} else if (temp == 2) { // 치킨집
chickenCount++;
chickenAddress.add(new int[]{i, j});
}
}
}
// 치킨집과 집 간 거리 저장 배열
chicken = new int[chickenCount][houseCount];
selected = new boolean[chickenCount];
// 치킨집과 집 사이의 거리 계산
howFarChicken(chickenAddress, houseAddress);
// 백트래킹 시작
dfs(0, 0);
// 결과 출력
System.out.println(minChicken);
}
}
체크 포인트
- 전역 변수를 많이 선언을 해도 괜찮은 건가?
- 입력받는 것이 아직 많이 서툴다. 어렵다.
- 스트림에서 sum을 계산한것
- 배열을 최대 2차원만 구상한 것.
