🔵 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/49994?language=cpp
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
💡 Point
- 특정 구역이 아닌 [한 구역에서 다른 구역으로 가는 길]을 구하는 것이다.
- 중복 경로는 무시한다.
🔷 특정 구역이 아닌 [한 구역에서 다른 구역으로 가는 길]을 구하는 것이다.
처음에는 도착 구역을 기준으로 코드를 작성했다. 하지만 이렇게 짤 경우 문제가 있다.
A -> B, C -> B일 때, 각각 다른 경로임에도 불구하고 A -> B 에서 먼저 B를 방문했으므로 C -> B는 카운트하지 않는 것이다.
이때, 도착 구역이 아닌 방향의 필요성을 알게 되었다.
따라서 (출발점, 갈 방향)으로 map[x][y][dir]을 구성하고, 입력으로 들어온 커맨드를 적용하여 문제를 풀면 된다.
🔷 중복 경로는 무시한다.
map[x][y][dir]로 구현할 경우 중요한 점이 하나 있다.
바로 중복 경로는 무시한다는 것이다.
이 말은 A -> B, B -> A 경로를 각각 따로 세지 않는다는 말을 의미한다.
중복 경로를 무시한 채 답을 구하려면, 로직 중간에 map[x][y][opposite dir]의 방문 여부도 true로 표시해 줘야 한다.
🔷 반대 방향 구하기
// 상 하 좌 우
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int opposite = i ^ 1;
상(0), 하(1) /// 좌(2) 우(3)
이런 식으로 반대 방향이 숫자로 이어지게 dx, dy를 설정하면 ^(XOR) 연산으로 반대 방향을 손쉽게 구할 수 있다.
| dir | dir ^ 1 |
| 0 | 1 |
| 1 | 0 |
| 2 | 3 |
| 3 | 2 |
하지만
좌(0) 상(1) 우(2) 하(3)
과 같은 경우는 XOR 연산이 통하지 않는다.
이럴 때에는 모듈러 연산을 통해 쉽게 반대 방향을 얻을 수 있다.
int opposite = (i + 2) % 4;
🔵 전체 코드
#include <string>
#include <iostream>
using namespace std;
// 상 하 좌 우
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
bool map[11][11][4];
int findIndex(char c)
{
if (c == 'U') return 0;
else if (c == 'D') return 1;
else if (c == 'L') return 2;
else return 3;
}
// (출발점, 갈 방향)을 기준으로 작성
int solution(string dirs) {
int answer = 0;
pair<int, int> pos = { 5, 5 };
for (char c : dirs)
{
int i = findIndex(c);
int opposite = i ^ 1;
int nx = pos.first + dx[i];
int ny = pos.second + dy[i];
if (nx < 0 || nx > 10 || ny < 0 || ny > 10) continue;
if (map[pos.first][pos.second][i] == false && map[nx][ny][opposite] == false)
{
answer++;
map[pos.first][pos.second][i] = true;
map[nx][ny][opposite] = true;
}
pos = { nx, ny };
}
return answer;
}
🔵 시간 복잡도
for문에서 dirs의 길이만큼 순회하므로, dirs의 길이가 N일 때 시간 복잡도는 O(N)이다.
'PS' 카테고리의 다른 글
| [C++] Programmers Lv. 2 "짝지어 제거하기" (0) | 2025.04.29 |
|---|---|
| [C++] Programmers Lv. 2 "괄호 회전하기" (1) | 2025.04.25 |
| [C++] Programmers Lv. 1 "실패율" (0) | 2025.04.23 |
| [C++] Programmers Lv. 2 "행렬의 곱셈" (0) | 2025.04.22 |
| [C++] Programmers Lv. 1 "모의고사" (0) | 2025.04.18 |