-
[윈터코딩] 방문길이알고리즘/윈터코딩 2020. 10. 29. 00:37
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; }
'알고리즘 > 윈터코딩' 카테고리의 다른 글
[윈터코딩] 스킬트리 (0) 2020.10.29 [윈터코딩] 지형이동 (0) 2020.10.29 [윈터코딩] 멀쩡한 사각형 (0) 2020.10.27