[Programmers] Lv2. 방문 길이 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

어려운 구현 문제가 아닌데, 점이 아닌 선분(line) 처리가 까다로운 문제였네요. 선분은 두 개의 점(Point)으로 이루어져 있으니, map을 통해 <시작점, 끝 점들>을 관리하였습니다. 끝 점들이라고 표현해놨는데, 플레이어가 한 번에 움직일 수 있는 최대 칸수는 1칸이므로, 점 하나당 가질 수 있는 선분의 종류는 4가지(상, 하, 좌, 우)입니다.

 

 

제가 구현한 로직을 시나리오대로 한번 보도록 하죠. "UUDL"을 한 번 예시로 보겠습니다.

 

1. [U] 출발지(0, 0)에서 한 칸 위로 올라가고, 해당 선분을 map에 등록합니다.

• 도착지(0, 1)에서 출발지(0, 0)까지의 선분도 같은 선분이므로, 출발지와 도착지 순서를 변경한 것도 map에 등록해줍니다. 이 부분은 모든 이동에서 똑같이 적용됩니다.
• 등록된 선분들 중에 현재 선분이 없다면 answer + 1을 해줍니다.

 

 

2. [U] (0, 1) \( \rightarrow \) (0, 2)로 이동하여 똑같이 map에 등록합니다.

 

 

3. [D] (0, 2) \( \rightarrow \) (0, 1)로 이동하지만, 이 선분은 끝 점에 등록된 선분이므로 카운트 X

 

 

4. [L] (0, 1) \( \rightarrow \) (-1, 1)로 이동해줍니다.

 

 

이로써 answer = 3으로 답을 도출할 수 있습니다.

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
#include <map>
using namespace std;
const int MAX_LENGTH = 11;

struct Point {
	Point() { }
	Point(int row, int col) : _row(row), _col(col) { }

	bool operator<(const Point& other) const {
		if (_row == other._row)
			return _col < other._col;
		return _row < other._row;
	}

	bool operator==(const Point& other) const {
		return _row == other._row and _col == other._col;
	}

	int _row;
	int _col;
};

map<char, Point> directions {  {'U', {-1, 0 }}, { 'D', {1, 0} }, { 'R', {0, 1} }, { 'L', {0, -1} }  };


class Record {
public:
	void Insert(const Point& otherStart, const Point& otherEnd) {
		auto iter = _lines.find(otherStart);
		
		/* 두 선분의 시작점이 같다면, 끝 점을 비교해본다. */
		if (iter != _lines.end()) {
			for (const auto myEndPoint : iter->second) {
				if (myEndPoint == otherEnd)
					return;
			}
		}

        // 점 A, B가 있다면 A-B, B-A는 같은 선분이므로 둘 다 추가
		_lines[otherStart].push_back(otherEnd);
		_lines[otherEnd].push_back(otherStart);
		_firstStepCount++;
	}

	int GetAnswer() { return _firstStepCount; }
private:
	map<Point, vector<Point>> _lines;    // <시작점, 끝 점들>
	int _firstStepCount = 0;
};


int solution(string dirs) {
	int firstStepCount = 0;
	int halfLine = MAX_LENGTH / 2;

	Point player(halfLine, halfLine);
	Record record;

	for (const auto instruction : dirs) {
	int nextRow = player._row + directions[instruction]._row;
	int nextCol = player._col + directions[instruction]._col;

	if (nextRow < 0 or nextRow >= MAX_LENGTH or nextCol < 0 or nextCol >= MAX_LENGTH)
		continue;

	Point start = player;
	Point end = player = Point(nextRow, nextCol);
	
	record.Insert(start, end);
	}

	return record.GetAnswer();
}