https://school.programmers.co.kr/learn/courses/30/lessons/49190?language=cpp
๋ฌธ์ ์ค๋ช
์์ (0,0)์์ ์์ํด์ ์๋์ฒ๋ผ ์ซ์๊ฐ ์ ํ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ๋ฉฐ ์ ์ ๊ธ์ต๋๋ค.
ex) 1์ผ๋๋ ์ค๋ฅธ์ชฝ ์๋ก ์ด๋
๊ทธ๋ฆผ์ ๊ทธ๋ฆด ๋, ์ฌ๋ฐฉ์ด ๋งํ๋ฉด ๋ฐฉํ๋๋ก ์๋๋ค.
์ด๋ํ๋ ๋ฐฉํฅ์ด ๋ด๊ธด ๋ฐฐ์ด arrows๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ฐฉ์ ๊ฐฏ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์ธ์.
- ๋ฐฐ์ด arrows์ ํฌ๊ธฐ๋ 1 ์ด์ 100,000 ์ดํ ์ ๋๋ค.
- arrows์ ์์๋ 0 ์ด์ 7 ์ดํ ์ ๋๋ค.
- ๋ฐฉ์ ๋ค๋ฅธ ๋ฐฉ์ผ๋ก ๋๋ฌ ์ธ์ฌ์ง ์ ์์ต๋๋ค.
๊ตฌํ ์์ฒด๋ ์ด๋ ต์ง ์๋ค.
๋ค๋ง ํ๋ฒ ๋ฐฉ๋ฌธํ๋ ๋ ธ๋๋ฅผ ๋ค๋ฅธ ๊ฒฝ๋ก์์ ๋ค์ ๋ฐฉ๋ฌธํ๊ฒ ๋๋ฉด ๋ฐฉ์ด ๋ง๋ค์ด์ง๋๋ฐ,
map์ ์ฌ์ฉํด์ node, edge์ ๋ฐฉ๋ฌธ์ ์ฒดํฌํ๋ ๊ฑธ ๋ ์ฌ๋ฆฌ๋๊ฒ ํ๋ค์์
๋๊ฐ์ ์ผ๋ก ๊ฐ๋ก์ง๋ฅด๋ X ๋ชจ์์ ๋ฐฉ์ด ์๊ธธ ๊ฒฝ์ฐ๋ฅผ ์ํด
arrow ๊ฐ์ ๋๋ฒ ์ด๋์์ผ์ฃผ๋ ์์ด๋์ด๊ฐ ์ค์ํ ๊ฒ ๊ฐ๋ค.
์ด๊ฑด ๋๋ ๊ตฌ๊ธ๋งํด์ ์์๋ธ๊ฑฐ....ใ
๋์ ํ์ด
#include <string>
#include <vector>
#include <map>
using namespace std;
int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int solution(vector<int> arrows) {
map<pair<int, int>, bool> nodeVisited;
map<pair<pair<int, int>, pair<int, int>>, bool> edgeVisited;
int answer = 0;
int x = 0;
int y = 0;
nodeVisited[{x,y}] = true;
for (int i = 0; i < arrows.size(); i++){
int dir = arrows[i];
for (int j = 0; j < 2; j++){
int nx = x+dx[dir];
int ny = y+dy[dir];
if(nodeVisited[{nx,ny}]==true && edgeVisited[{{x,y},{nx,ny}}]==false){
answer++;
}
else {
nodeVisited[{nx,ny}]=true;
}
edgeVisited[{{x,y},{nx,ny}}]=true;
edgeVisited[{{nx,ny},{x,y}}]=true;
x=nx;
y=ny;
}
}
return answer;
}
'๐ ์๊ณ ๋ฆฌ์ฆ > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/PGS] Lv.1 : ์ฑ๊ฒฉ ์ ํ ๊ฒ์ฌํ๊ธฐ (์นด์นด์ค ๊ธฐ์ถ) (0) | 2023.04.12 |
---|---|
[C++/PGS] Lv.1 : ๊ฐ์ธ์ ๋ณด ์์ง ์ ํจ๊ธฐ๊ฐ (์นด์นด์ค ๊ธฐ์ถ) (0) | 2023.04.12 |
[C++/PGS] Lv.3 : N์ผ๋ก ํํ (DP) (0) | 2023.03.03 |
[C++/PGS] Lv.3 : ์์ (๊ทธ๋ํ/Floyd-Warshall) (1) | 2023.03.03 |
[C++/PGS] Lv.3 : ๊ฐ์ฅ ๋จผ ๋ ธ๋ (๊ทธ๋ํ/bfs) (0) | 2023.03.03 |