[Algorithm] 화이트 칼라 (Algospot – WHITECOLLAR)

출처

https://algospot.com/judge/problem/read/WHITECOLLAR

난이도

하 – 중 – 상 – (최상) – 풀지 못함

문제

도둑이 특정 도시에서 출발해서 목적지 도시까지 최대한 빠른 길로 도망갈 예정이다. 도둑을 잡기 위해서 도둑이 방문할 도시를 미리 찾는 문제이다. 결과적으로 도시(Node)와 도시 간을 연결하는 길(Edge: 일방통행)이 주어졌을 때 Shortest Path를 찾는 문제이다.

후기

처음 문제를 읽고 Shortest Path를 찾는 문제로 생각했다. 그래서 단순히 Stack을 사용해서 Shortest Path 하나를 찾도록 코딩을 했다. 하지만, 문제에 숨겨진 의도를 제대로 파악하지 못하고 문제를 풀었다. 문제의 의도는 Shortest Path가 여러 개 있을 때는 모든 Short Path를 다 찾아야 하는 것이었다. 현재 나의 실력으로 최상 난이도 문제라고 생각한다. 이보다 어려운 문제는 풀지 못할 것 같다.
Shortest Path의 경우 동일한 도시를 2번 방문하는 경우가 없다. 그래서 Stack (First In First Out: FIFO)을 사용하여서 방문한 도시는 Stack에 추가하였다. 그리고 순서대로 Stack에서 Pop하여서 다음 방문 도시를 탐색하면 된다. 처음에는 단순히 Pop을 하고 한번 방문한 도시를 다시 방문하지 않기 때문에 동일한 도시를 방문하는 경우 계산을 하지 않았다. 하지만 그렇게 하면 동일한 길이를 가진 경로를 모두 계산하지 않게된다. 예를 들어 1 -> 2 -> 4 -> 5로 가는 방법과 1 -> 3 -> 4 -> 5로 가는 경로가 있으면 두개중 먼저 5번에 방문하는 경로만 검색을 하게 된다.
여러개의 Path를 계산하기 위해서 같은 Path의 길이를 가진 길이 여러 개 있으면 방문 도시의 개수를 Merge 하는 부분이 필요하다. 위 예의 경우 4번 도시(Node)에 방문하는 2가지 경우를 하나로 Merge 하여 다음 계산을 수행하면 된다.
처음에는 방문 도시를 확인하기 위해서 단순 Integer 리스트를 사용했다. 실행시간을 단축하고 싶어서 Bit 연산을 사용하여 Integer 리스트 크기를 최소화했다. 이 부분에서 대략 30ms 정도 시간이 단축되었다.
결과적으로 같은 길이를 가진 여러 개의 Path를 계산해야 하므로 난이도 높았던 문제라고 생각한다. 특히, Algospot의 경우 몇 개의 오답이 발생했는지 등을 확인할 수 없어서 문제를 해결하는 데 더 어려움이 있는 것 같다. 개인적으로 코딩을 연습하는 관계로 Stack부터 모든 부분을 다 작성하였다. 하지만, 이미 잘 만들어진 std::vector 등을 사용하면 더 효율적으로 코딩을 할 수도 있는 것 같다. 아마 실행시간도 많이 단축될 것으로 생각된다.
추가: White-Collar의 의미가 궁금해서 네이버에 검색을 해보았다. 화이트 칼라는 “정신적·지적 노동을 주체로 하는 근로자의 속칭으로 전문직·기술직·관리직·사무직 종사자”를 의미한다. 문제의 White-Collar 제목과 문제의 연관성을 잘 모르겠다.

코드

Stack을 사용하여 Shortest Path를 탐색하는 코드
실행 시간: 96ms (제일 빠른 실행 시간 대비 30ms (3배 느림))

//MK: WhiteCollar 문제 해결 코드
#include <stdio.h>
#include <string.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable:4996)

#define MAXCITY 1001
#define MAXROAD 50001
#define MAXBIT 33

int allRoads[MAXROAD][2];

typedef struct cityInfo {
	int counter;
	int visitedInfo[MAXBIT];
}node;

node list[MAXCITY];
int numCity;
int numRoad;

int stack[MAXCITY];
int stackPtr;
int stackEnd;

int answer[MAXCITY];

//MK: Stack 초기화 및 시작 Node를 추가하는 부분
void init() {
	stackPtr = 0;
	stackEnd = 0;
	for (int i = 1; i <= numCity; i++) {
		answer[i] = 0;
		list[i].counter = 0;
		memset(list[i].visitedInfo, 0, sizeof(int) * MAXBIT);
		if (i == 1) {
			list[i].counter = 1;
			list[i].visitedInfo[0] = 1 << 1;
		}
	}
	stack[stackEnd] = 1;
	stackEnd++;
}

//MK: 단순히 Node를 복사하는 부분
void copyNode(int srcPtr, int desPtr) {
	node *src = &list[srcPtr];
	node *des = &list[desPtr];
	des->counter = src->counter;
	for (int i = 0; i < MAXBIT; i++) {
		des->visitedInfo[i] = src->visitedInfo[i];
	}
}

//MK: Node의 Visited 도시 정보만 복사
void copyNodeListOnly(int srcPtr, int desPtr) {
	node *src = &list[srcPtr];
	node *des = &list[desPtr];
	for (int i = 0; i < MAXBIT; i++) {
		des->visitedInfo[i] |= src->visitedInfo[i];
	}
}

//MK: Stack에 추가하는 부분
void insertStack(int srcPtr, int desPtr) {
	if (list[desPtr].counter == 0) {
		copyNode(srcPtr, desPtr);
		node *des = &list[desPtr];
		int ptr = desPtr / 31;
		int rem = desPtr % 31;
		des->visitedInfo[ptr] |= 1 << rem;
		des->counter++;
		stack[stackEnd] = desPtr;
		stackEnd++;
		if (stackEnd >= MAXCITY - 1) {
			stackEnd = 0;
		}
	}
	else {
		node *src = &list[srcPtr];
		node *des = &list[desPtr];
		if ((src->counter + 1) == des->counter) {
			copyNodeListOnly(srcPtr, desPtr);
		}
	}
}

//MK: Stack에 Pop하는 부분
int popStack() {
	if (stackPtr == stackEnd) {
		return -1;
	}
	int ret = stack[stackPtr];
	stackPtr++;
	if (stackPtr >= MAXCITY - 1) {
		stackPtr = 0;
	}
	return ret;
}

//MK: Stack을 사용하여 문제를 해결하는 부분
void findResult() {
	int minValue = 0;
	while (1) {
		int ptr = popStack();
		if (ptr == -1) {
			return;
		}
		for (int i = 0; i < numRoad; i++) {
			//MK: 이부분 엄청난 Overhead로 작용함
			//MK: 이부분에서 빨리 끝나기 때문에 실행시간이 빨라 질것이라 판단했으나, 매번 검사하는 Overhead가 더 큰것 같음
			/*if (minValue != 0 && minValue < list[ptr].counter) {
				return;
			}*/ 
			if (allRoads[i][0] == ptr) {
				if (allRoads[i][1] == numCity) {
					if (minValue != 0 && minValue != list[ptr].counter) {
						return;
					}
					insertStack(ptr, numCity);
					if (minValue == 0) {
						//answer[numCity] = 1;
						int ans = numCity / 31;
						int rem = numCity % 31;
						list[numCity].visitedInfo[ans] |= (1 << rem);
						minValue = list[ptr].counter;
					}
				}
				else {
					insertStack(ptr, allRoads[i][1]);
				}
			}
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);

	int testCase;
	scanf("%d", &testCase);
	for (int m = 1; m <= testCase; m++) {
		scanf("%d %d", &numCity, &numRoad);
		init();
		for (int i = 0; i < numRoad; i++) {
			scanf("%d %d", &allRoads[i][0], &allRoads[i][1]);
		}
		findResult();
		for (int i = 1; i <= numCity; i++) {
			int ptr = i / 31;
			int rem = i % 31;
			int tmp = (list[numCity].visitedInfo[ptr] & (1 << rem));
			if (tmp > 0)
				printf("%d ", i);
		}
		printf("\n");
	}

	return 0;
}

출처

https://terms.naver.com/entry.nhn?docId=473831&cid=42120&categoryId=42120

Leave a Comment Cancel reply