JArchive 프로그래밍 일기

등굣길 문제링크 

리뷰 

최단 경로를 세야 하니까 오른쪽 또는 아래로만 이동해야 한다. 

그래서 특정 지점까지 몇번을 거쳐 가는지 점화식을 세야 한다. 

웅덩이가 있으면 최단경로를 세면 안되니까 처음부터 -1로 초기화 해둔다. 

현재 지점 기준으로 위, 또는 왼쪽의 최단경로를 기반으로  현재 지점의 최단경로를 계산한다. 

인덱스에 음수가 발생하지 않도록 (1, 1)을 시작점으로 두고 (1, 1)의 최단경로를 1로 초기화한다. 

핵심 코드는 아래와 같다

temp_a = (위칸이 음수가 아니라면, ) D[a-1][b] 
temp_b = (왼쪽칸이 음수가 아니라면, ) D[a][b-1] 

D[a][b] = (temp_a + temp_b) % div_num;

맞았습니다 코드 

#include <string>
#include <vector>

using namespace std;
int D[101][101]; // 최단거리를 저장할 배열
int div_num = 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {

  for(auto v : puddles){
    D[v[1]][v[0]] = -1; // 물웅덩이를 -1로 초기화
  }
  D[1][1] = 1;

  for(int i = 1; i <= n; i++){ // n: 행
    for(int j = 1; j <=m; j++){ // m: 열
      if(D[i][j] == -1) continue;
      int temp_a = 0, temp_b = 0;

      if(D[i-1][j] != -1) temp_a = D[i-1][j];
      if(D[i][j-1] != -1) temp_b = D[i][j-1];

      D[i][j] += (temp_a + temp_b) % div_num;
    }
  }

  return D[n][m];
}

문제 링크 

리뷰 

처음에 감을 못잡은 문제... 어떤 파라미터 넘겨서 탐색해야되지? 다음에 다시 풀어봐야겠다. 

맞았습니다 코드 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int global_N, target_number;
int max_cnt = 8;
int min_cnt = 1 + max_cnt;

void dfs(int cur_num, int cnt){ // (현재 숫자, N을 사용한 개수)
  if(cnt > max_cnt) return;
  else if(cur_num == target_number){
    min_cnt = min(cnt, min_cnt);
    return;
  }

  int n = 0;  // 계산할 숫자 n 
  for(int i = 1; i <= 6; i++){ // N을 1개~6개 사용가능
    // 계산할 숫자 n -> N, NN, NNN
    n = n*10 + global_N;
      
    dfs(cur_num + n, cnt + i);
    dfs(cur_num - n, cnt + i);
    if(cur_num != 0 || cnt > 8){
      dfs(cur_num * n, cnt + i);
      dfs(cur_num / n, cnt + i);
    }
  }
}

int solution(int N, int number) {
  global_N = N;
  target_number = number;
  dfs(0, 0);
  return (min_cnt == 9) ? -1 : min_cnt;
}

문제 링크 

리뷰 

항상 가장 작은 수와, 그 다음 작은 수가 필요해서 자동으로 정렬해주는 우선순위 큐를 이용했다. 

우선순위 큐에서 front()를 first로 받고, pop()후에 front()를 second로 받으면 쉽게 접근할 수 있다. 

항상 2개를 꺼내니까 pop()을 2번 해줘야하는 것을 유의하자. 

전부 스코빌지수가 K가 됬는지는 큐의 크기가 1이 됬을 때 검사한다. 

마지막 남은 원소가 K 미만이라면 answer 는 실패다. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> scoville, int K) {
  int answer = 0;
  bool result = true;

  priority_queue<int, vector<int>, greater<int>> pq;

  for(auto s : scoville){ pq.push(s); }

  while(!pq.empty()){

    if(pq.top() > K) break; // 더 검사하지 않아도 된다
    if(pq.size() == 1 && pq.top() < K) { result = false; break; } // 실패

    int first = pq.top();
    pq.pop();
    int second = pq.top();
    pq.pop();

    pq.push(first + (second * 2));
    // cout << "first: " << first << " second:" << second << ' ';
    answer++;
  }
  if(!result) answer = -1;
  return answer;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int k = 7;
  vector<int> scofille = {1, 2, 3, 9, 10, 12};
  cout << solution(scofille, k);

  return 0;
}

문제 링크 

문제 유의 사항

반드시 모든 티켓을 사용해야 한다. 

반드시 시작 공항은 ICN 이다. 

모든 티켓을 사용할 수 있는 입력만 주어진다. 

가능한 경로가 여러개 나와도, 알파벳순으로 우선하는 경로를 선택한다. (== 탐색 전 정렬 필요) 

리뷰 

DFS 구현 시, 탐색 함수 매개변수와 종료 조건이 중요하다. 

탐색 목표 : 목적지, 몇번째 방문인지. 

탐색 종료 조건 : 티켓 개수가 방문 순서와 똑같으면 모든 티켓을 사용한 것이니까 종료. 

탐색 가능 조건 : 목적지를 시작점으로 하는 티켓이 있는지 확인 && 미방문인지 확인 

1) 모든 티켓을 검사. 

탐색 가능 조건이 있다면, 방문 표시하고 답 벡터에 넣는다. DFS 탐색 시작. 

DFS탐색은 true/ false 를 리턴한다.

탐색 해보고 만약 실패라면, 다시 미방문 표시 

2) 탐색 가능 조건이 없다면, 답 벡터에서 빼고 false 리턴. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

vector<string> routes; // 정답 경로 벡터
bool visit[100002]; // 방문 체크

bool DFS(string start, int cnt, vector<vector<string>> &tickets){

  if(cnt == tickets.size()) return true; // 탐색 끝나면 true

  for(int i = 0; i < tickets.size(); i++){ // 시작점 타겟이 있는지 확인 
    if(visit[i] == false && start == tickets[i][0]){ // 미방문이고, 시작점 타겟이 맞으면, 방문!
      visit[i] = true;
      routes.push_back(tickets[i][1]); // 방문한 도착지를 답 벡터에 푸시
      bool res = DFS(tickets[i][1], cnt+1, tickets);
      if(res) return true;
      visit[i] = false;
    }
  }
  
  routes.pop_back(); // 갈 곳이 없으면, 가장 최근 도착지를 벡터에서 제거 
  return false;
}

vector<string> solution(vector<vector<string>> tickets) {

  sort(tickets.begin(), tickets.end()); // 알파벳 순 앞서는 경로 선택
  routes.push_back("ICN"); // 항상 시작은 ICN
  DFS("ICN", 0, tickets);  //시작점이 "ICN"인 티켓을 탐색

  return routes;
}

문제 링크 

첫 번째 풀이 : 시작점을 기준으로 정렬했다.

end_point는 차가 나가는 지점을 저장한다. 

answer 는 감시카메라 개수 변수다. 

차 2대가 {1, 3} {4, 5} 이 순서로 오는 경우

두 차는 겹치지 않으니까 answer++ 로 카메라를 추가해줘야 한다. 

그리고 마지막 차가 나가는 지점은 5가 된다. end_point = r[1];

차 2대가 {1, 6} { 2, 3} 이 순서로 오는 경우

두 번째 차가 빨리 나가버린다. 

이 때는 종료지점이 더 짧은 3으로 end_point를 갱신해줘야 한다. 

차 2대가 {1, 6} { 2, 3} {4, 9} 이 순서로 오는 경우

 {1, 6} { 2, 3} 을 감시하는 카메라 말고, 하나 더 필요하다. 

새로운 차 { 4, 9 }를 감시하려면,  이미 감시한 {1, 6} 이 아니라, {2, 3}과 {4, 9}가 겹치는지를 확인해야 한다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> routes) {
  int answer = 1; // 차가 1대 이상이니까 카메라는 최소 개수 1
  int end_point = routes[0][1]; // 현재 차가 나가는 지점

  sort(routes.begin(), routes.end());
  for(auto r : routes){ // end_point: 현재 차,  r: 다음 차
    if(end_point < r[0]){ // 현재 차와 다음 차가 겹치지 않으면, 카메라 추가
      answer++;
      end_point = r[1]; // 다음 차 나가는 지점으로 갱신
    }

    // 현재 차가 end_point 보다 먼저 나간다면? 나가는 지점을 현재 차로 수정  
    if(r[1] <= end_point) end_point = r[1];
  }
  return answer;
}

두 번째 풀이 : 종료 지점으로 정렬했다. 

여기서는 감시카메라 개수를 0 으로 초기화 한다. 

마지막 지점은  end_point = -30001 ; 가장 작은 수로 초기화 한다. 

따라서 자동차가 1개 여도, 감시카메라 개수를 1 추가한다. 

주어진 배열

종료 지점이 빠른 순으로 정렬하면 아래와 같다. 

자동차 1개일 때는 첫 번째 자동차만 감시하면 된다.

여기서 감시카메라 개수는 1이다. 이때 end_point = -15 

두 번째 자동차 시작점은 -18이다.  end_point 보다 작다. 따라서 감시카메라를 추가하지 않아도 된다. 

세 번째 자동차의 시작점은 -14 니까 end_point 보다 크다. 감시카메라를 추가해야한다. 

이 때 end_point는 세 번째 자동차의 종료지점으로 갱신한다. 

end_point 는 자동차가 겹치는 마지막 지점으로 이해하면 수월하다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(vector<int> &a, vector<int> &b) {
  return a[1] < b[1]; // 종료 지점 기준으로 정렬
}

int solution(vector<vector<int>> routes) {
  int answer = 0;
  sort(routes.begin(), routes.end(), cmp);
  int end_point = -30001; // 초기값은 가장 작은 수

  for(auto r : routes){ // end_point: 현재 차,  r: 다음 차
    if(end_point < r[0]){
      answer++;
      end_point = r[1];
    }
  }
  return answer;
}

문제 링크 

DFS를 풀 때 매개변수를 줄면 코드 짜는 나도 덜 헷갈리고 메모리도 덜 소모한다. 

탐색할 때 불변하는 값은 전역변수로 해두었다. (컴퓨터 총 개수)

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

bool checked[202]; // 방문 체크 배열
int node_cnt; // 컴퓨터 총 개수

void dfs(int current, vector<vector<int>> &computers){
  checked[current] = true;

  for(int i = 0; i < node_cnt; i++){
    if(!checked[i] && computers[current][i] == 1) // 미방문이고 서로 연결됬다면 탐색하자 
      dfs(i, computers);
  }
}

int solution(int n, vector<vector<int>> computers) {
  int answer = 0;
  node_cnt = n; // 컴퓨터 개수를 전역변수로 만든다

  for(int i = 0; i < n; i++){ // 모든 노드에서 탐색 시작
    if(!checked[i]){ // 미방문이라면 탐색 시작
      answer++;
      dfs(i, computers);
    }
  }
  return answer;
}

문제 링크 

저번에 BFS로 푼 것을 DFS로 다시 풀어봤다.

DFS는 재귀함수의 매개변수를 뭐로 할지와 종료조건이 중요하다. 

문제 설명에 '최소'라는 단어가 나오면 BFS 또는 이분탐색으로 풀 수 있는 가능성이 있다. 

DFS로 이 문제를 풀 땐 아무래도 단어목록을 매개변수로 넘겨야 하다보니 BFS가 더 직관적이었다. 

DFS로 푼 코드 

#include <bits/stdc++.h>
using namespace std;

string tg; // 목표
int answer = 50;  // 최소 횟수 저장
bool checked[52]; // 단어 확인 여부

bool diff_one(string cur, string w){// 단어 cur와 w를 비교 
  int diff_cnt = 0;
  for(int i = 0; i < w.size(); i++){
    if(cur[i] != w[i]) diff_cnt++;
  }
  return (diff_cnt == 1); // 1글자만 다른 단어라면 true 
}

void dfs(string s, vector<string> words, int cnt){

  if(answer <= cnt) return; // 백트래킹 
  if(s == tg) { 
    answer = min(cnt, answer); // 타겟 찾았다면 최소 횟수를 갱신하고 종료
    return;
  }

  int w_len = words.size();
  for(int i = 0; i < w_len; i++){
  
    if(diff_one(s, words[i]) && !checked[i]){ // 1글자만 다르고, 확인 안해본 단어라면 
      checked[i] = true;
      dfs(words[i], words, cnt + 1);
      checked[i] = false;
    }
  }
}

int solution(string begin, string target, vector<string> words) {

  tg = target; // 시작단어와 타겟단어 전역변수
  dfs(begin, words, 0); // begin 단어부터 탐색 시작 
  if(answer == 50) answer = 0; // 타겟 못찾음
  return answer;
}