[윈터코딩] 방문길이

programmers.co.kr/learn/courses/30/lessons/49994

코딩테스트 연습 - 방문 길이

어떠한 사람들은 4차원 배열을 통하여 해결하였으나 나는 비트마스킹을 이용하여 문제를 해결하였다.

 

1, 해당 위치에서 이미 지나간 길의 정보를 저장하여야 하는데 map 이차원 배열에 해당 위치에서 위로 간 경우 1, 아래로 간 경우 2, 왼쪽으로 간 경우 4, 오른쪽으로 간 경우 8 을 저장하여 주고 & 연산자를 이용하여 지금 해당 위치에서 이동하려고 하는 길이 이미 지난 길인지 판별을 해 주웠다.

 

*주의 할 점

- 지금 위치와 다음 위치 둘 다 이미 지나간 길에 대한 정보를 갱신

- 범위를 넘어 섰는지 확인

 

소스코드

#include <cstdio>
#include <string>
using namespace std;

int map[20][20];
int answer = 0;

typedef struct info {
	int r;
	int c;
}info;

info up_action(info info) {
	int nr = info.r - 1;
	int nc = info.c;

	if (nr < 0 || nr > 10 || nc < 0 || nc > 10) return info;

	if ((map[info.r][info.c] & 1) == 0) {
		map[info.r][info.c] += 1;
		map[nr][nc] += 2;
		answer++;
	}

	return {nr,nc};
}

info down_action(info info) {
	int nr = info.r + 1;
	int nc = info.c;

	if (nr < 0 || nr > 10 || nc < 0 || nc > 10) return info;

	if ((map[info.r][info.c] & 2) == 0) {
		map[info.r][info.c] += 2;
		map[nr][nc] += 1;
		answer++;
	}

	return { nr,nc };
}

info left_action(info info) {
	int nr = info.r;
	int nc = info.c - 1;

	if (nr < 0 || nr > 10 || nc < 0 || nc > 10) return info;


	if ((map[info.r][info.c] & 4) == 0) {
		map[info.r][info.c] += 4;
		map[nr][nc] += 8;
		answer++;
	}

	return { nr,nc };
}

info right_action(info info) {
	int nr = info.r;
	int nc = info.c + 1;

	if (nr < 0 || nr > 10 || nc < 0 || nc > 10) return info;

	if ((map[info.r][info.c] & 8) == 0) {
		map[info.r][info.c] += 8;
		map[nr][nc] += 4;
		answer++;
	}

	return { nr,nc };
}

int solution(string dir) {

	int str_size = dir.size();

	info info = { 5,5 };

	for (int i = 0; i < str_size; i++) {
		if (dir[i] == 'U') {
			info = up_action(info);
		}
		if (dir[i] == 'D') {
			info = down_action(info);
		}
		if (dir[i] == 'L') {
			info = left_action(info);
		}
		if (dir[i] == 'R') {
			info = right_action(info);
		}
	}
	return answer;
}

int main() {
	printf("%d ", solution("LULLLLLLU"));
	return 0;
}