hyelie
hyelie
Hyeil Jeong
       
글쓰기    관리    수식입력
  • 전체보기 (495)
    • PS (283)
      • Algorithm (28)
      • PS Log (244)
      • Contest (6)
      • Tips (5)
    • Development (52)
      • Java (14)
      • Spring (23)
      • SQL (2)
      • Node.js (2)
      • Socket.io (3)
      • Study (4)
      • Utils (4)
    • DevOps (36)
      • Git (5)
      • Docker (4)
      • Kubernetes (2)
      • GCP (3)
      • Environment Set Up (8)
      • Tutorial (12)
      • Figma (2)
    • CS (74)
      • OOP (7)
      • OS (24)
      • DB (2)
      • Network (24)
      • Architecture (0)
      • Security (2)
      • Software Design (0)
      • Parallel Computing (15)
    • Project (15)
      • Project N2T (5)
      • Project ASG (0)
      • Project Meerkat (1)
      • Model Checking (7)
      • Ideas (2)
    • 내가 하고싶은 것! (34)
      • Plan (16)
      • Software Maestro (10)
      • 취준 (8)
hELLO · Designed By 정상우.
hyelie
PS/PS Log

22.06.16. 풀었던 문제들

PS/PS Log

22.06.16. 풀었던 문제들

1. 카드 짝 맞추기

너무 귀찮았다. 크게 3단계로 나눌 수 있는데

  • 현재 위치부터 1번 입력으로 이동할 수 있는 좌표 list 구하기
    • 구현으로 풀 수 있음
  • 현재 위치부터 모든 점까지 거리 구하기
    • 바로 위의 함수와 BFS를 이용해 풀 수 있음
  • backtrack으로 카드를 뒤집는 모든 종류를 구하기
    • 한 카드를 뒤집으면 그 카드의 pair도 바로 뒤집는 게 제일 효율적이다. 따라서 한 카드를 뒤집고자 하면 '현재 위치 ~ 그 카드의 위치' + '그 카드의 위치 + 그 카드의 pair의 위치' + 2만큼의 count가 더해진다. 이걸 이용해 backtrack하면 된다.

 

// 카드 짝 맞추기
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <iostream>
#include <queue>
using namespace std;
int boardsize = 4;
int INF = 999999;
int answer = INF;
typedef pair<int, int> pii; // .fisrt : r, .second : c
typedef pair<pii, pii> ppiipii;
vector<vector<int>> boards; // board
vector<pii> cards; // cards[i] : i번째 카드
map<pii, pii> mapper; // mapper[pii] : 해당 pii의 짝
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
// cur부터 1번 입력으로 이동 가능한 list return
vector<pii> getMoveablePoints(pii cur){
vector<pii> result;
// 상하좌우
for(int i = 0; i<4; i++){
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
if(0 <= nr && nr < boardsize && 0 <= nc && nc < boardsize){
result.push_back({nr, nc});
}
}
// ctrl + 상하좌우
for(int i = 0; i<4; i++){
int nr = cur.first, nc = cur.second;
bool flag = false; // flag : 해당 방향으로 이동했을 때 열린 카드가 있는지
do{
nr += dr[i];
nc += dc[i];
// 만약 범위 벗어나면 break
if(!(0 <= nr && nr < boardsize && 0 <= nc && nc < boardsize)){
result.push_back({nr - dr[i], nc - dc[i]});
break;
}
// 카드 있는 경우 해당 카드를 넣음
if(boards[nr][nc] != 0){
result.push_back({nr, nc});
flag = true;
break;
}
}while(0 <= nr && nr < boardsize && 0 <= nc && nc < boardsize);
}
return result;
}
// cur부터 모든 점까지 거리 리턴. BFS 이용
vector<vector<int>> get_dist(pii cur){
vector<vector<int>> dist(boardsize, vector<int>(boardsize, INF)); // dist[r][c] : cur부터 {r, c}까지 거리
vector<vector<bool>> visited(boardsize, vector<bool>(boardsize, false)); // visited[r][c] == true : 방문된 것
queue<pair<pii, int>> q; // .first : 좌표, .second : cur부터 해당 좌표까지 거리
q.push({cur, 0});
dist[cur.first][cur.second] = 0;
visited[cur.first][cur.second] = true;
while(!q.empty()){
pii top = q.front().first;
int topdist = q.front().second;
q.pop();
// top으로부터 갈 수 있는 모든 것들 : 상하좌우, 상하좌우가장가까운카드 or 가장마지막칸
vector<pii> moveables = getMoveablePoints(top); // 함수를 이용해 구함
for(pii moveable : moveables){
if(visited[moveable.first][moveable.second] == false){ // unvisited라면 해당 칸 탐색
q.push({moveable, topdist + 1});
visited[moveable.first][moveable.second] = true;
dist[moveable.first][moveable.second] = topdist+1;
}
}
}
return dist;
}
void DFS(int cur_r, int cur_c, int cur_cnt, vector<bool> visited){
if(answer < cur_cnt) return;
int clear = true; // clear : 모든 open card가 closed인지 검사
for(bool b : visited){
if(b == false){
clear = false;
break;
}
}
if(clear == true){ // clear라면 정답 갱신
answer = min(answer, cur_cnt);
return;
}
vector<vector<int>> dist_from_cur_to_all = get_dist({cur_r, cur_c}); // cur부터 모든 점까지 입력 개수
for(int i = 0; i<visited.size(); i++){ // card로 backtrack
if(visited[i] == false){ // unvisited인 것들에 대해 DFS
// cards[i] : 현재 탐색할 카드
pii paircard = mapper[{cards[i].first, cards[i].second}]; // card의 짝
vector<vector<int>> dist_from_card_to_all = get_dist({cards[i].first, cards[i].second}); // card부터 모든 점까지 입력 개수
int paircardidx = find(cards.begin(), cards.end(), paircard) - cards.begin(); // card 짝의 index
visited[i] = visited[paircardidx] = true;
int backup = boards[paircard.first][paircard.second];
boards[cards[i].first][cards[i].second] = boards[paircard.first][paircard.second] = 0;
// 다음 DFS할 때는 '현 위치 ~ cards[i]' + 'cards[i] ~ paircard(cards[i]의 pair)' + 2(엔터 2번)을 더해 주어야 함.
DFS(paircard.first, paircard.second, cur_cnt + dist_from_cur_to_all[cards[i].first][cards[i].second] + dist_from_card_to_all[paircard.first][paircard.second] + 2, visited);
visited[i] = visited[paircardidx] = false;
boards[cards[i].first][cards[i].second] = boards[paircard.first][paircard.second] = backup;
}
}
}
int solution(vector<vector<int>> board, int r, int c) {
boards = board;
vector<vector<pii>> pairs(7); // pairs[i][0], pairs[i][1]은 서로 pair
for(int r = 0; r<boardsize; r++){
for(int c = 0; c<boardsize; c++){
if(board[r][c] != 0){
cards.push_back({r, c});
pairs[board[r][c]].push_back({r, c});
}
}
}
vector<bool> visited(cards.size(), false); // visited[i] : true if ith card used
for(vector<pii> v : pairs){
if(v.size() == 0) continue;
mapper[v[0]] = v[1];
mapper[v[1]] = v[0];
}
DFS(r, c, 0, visited);
return answer;
}
// 이것도 backtrack인 것 같은데...
// 모든 카드 위치 넣고 탐색 !

 

 

오늘은 graph 알고리즘 정리에 힘쓰고 있다. 지금까지 미뤄둔 TODO들, 주말이나 출근 안하는 날에 적어도 하나하나씩 정리해 가자! 지금 union-find, MST, topological sort, master theorem 남아있다. 하루 1개씩만 해도 다 끝낼 수 있으니까 귀찮아도 나중에 코드 그대로 쓸 거니까 깔끔하게 정리하자!

​

​

2. 백준 1753 최단 경로

dijkstra 구현 문제

​

​

3. 백준 11657 타임머신

bellman-ford 구현 문제

​

​

4. 백준 11404 플로이드

floyd-warshall 구현 문제

'PS > PS Log' 카테고리의 다른 글

22.06.18. 풀었던 문제들  (0) 2022.06.23
22.06.17. 풀었던 문제들  (0) 2022.06.23
22.06.15. 풀었던 문제들  (0) 2022.06.23
22.06.14. 풀었던 문제들  (0) 2022.06.23
22.06.13. 풀었던 문제들  (0) 2022.06.23
    hyelie
    hyelie

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.