문제링크 : https://programmers.co.kr/learn/courses/30/lessons/49190


아이디어

  • 사방이 막히는 경우
    • 이미 지난 점을 다시 지나올때, 단, 이전에 도착한 방향과 똑같지 않아야함
      • 지난점을 체크하고
      • 지나온 방향도 체크해야함, 이때 역방향도 체크
    • X자를 그리며 화살표가 이동하는 경우
      • 점을 2번 이동하는 걸로 하자
      • 방이 최대 200000
      • 중복체크할때 배열로 하면 너무커짐
      • map으로 중복 체크하자

시간복잡도 계산

  • 배열 크기 전체 순회 : O(N)

자료구조

  • 중복체크 : map<pair<int, int>, bool>
    • 들어가는값 : 각각 y,x축 좌표
    • 최소값 : -2e5
    • 최대값 : 2e5
      • 중복 방향 체크 : map<tuple<int, int, int, int>,bool>
      • int pre : 이전 방향을 확인

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <map>
#include <tuple>
 
using namespace std;
 
map<pair<int, int>, bool> chk;
map<tuple<int, int, int, int>, bool> dirchk;
 
int dy[] = {-1,-1,0,1,1,1,0,-1};
int dx[] = {0,1,1,1,0,-1,-1,-1};
 
int solution(vector<int> arrows) {
    int cnt=0;
    
    int y = 0;
    int x = 0;
    chk[make_pair(y,x)] = 1;
    
    
    for(int i=0; i<arrows.size(); i++) {
        int tmp = 2;
        while(tmp--) {
            int ed = arrows[i];
            
            int ny = y + dy[ed];
            int nx = x + dx[ed];
            
            // 도착점이 중복값이면서, 같은 방향이 아닐경우
            if(chk[make_pair(ny,nx)] && dirchk[{ny,nx,y,x}] ==false) {
                cnt++;
            }
            
            chk[{ny, nx}] = 1;
            dirchk[{ny,nx,y,x}] = 1;
            dirchk[{y,x,ny,nx}] = 1;
            
            y = ny;
            x = nx;
        }
        
    }
    return cnt;
}
 
cs

문제유형

  • 시뮬레이션 - 새로생기는 영역 구하기
    • 새로 영역 생기는 경우 : 이미 지나온 간선 && 같은 방향으로 들어오지 않아야함
    • map 사용할경우 노드 너무많아지고, 음수 사용하기 위해 map 사용

+ Recent posts

티스토리툴바