침대 밖은 위험해!

Lannegar Valley, Lannegar(City)의 퀘스트는 앞글 참조

2017/12/22 - [일상다반사/게임] - [Exiled Kingdoms] 공략 - Lannegar Valley, Lannegar(City)

2017/12/25 - [일상다반사/게임] - [Exiled Kingdoms] 공략 - Lannegar Valley, Lannegar(City) 2

제 주관적으로 쓰는 글입니다.

해당편 퀘스트 순서

- A Warrior's Hornor

- Hunting bugs!

- A Wild Mystery

1. North Bluemist River

- 오늘 퀘스트를 수행할 장소 입니다.

2. 추천 퀘스트 순서 및 퀘스트 획득, 클리어 방법

1) A Warrior's Hornor

- 왼쪽 던전 맵에서 노란색 표시된 곳으로 가면 오른쪽 그림처럼 시체가 있습니다.

- 퀘스트를 안받으면 반지가 없으니 꼭 받고 가도록 합니다.

  받았는데도 없다!! 하시면 퀘스트를 받기전에 해골을 한번 보고 왔을 가능성이 높으니 퀘스트를 받고 저장했다가 다시 시작하면 됩니다.

- 해골에서 반지를 줍줍하고 Garissenda 에게 되돌려 줍니다.

- 왼쪽 그림처럼 그럼 내 파티에 같이 넣을 수 있는데 경험치 20% 뺏김....

- Azaph's Ring of Element는 용병 상태창에서 빼서 내가 차면 됩니다.

- 해당 던전에는 비밀문이 2개 있습니다.

- 1번은 그냥 가도 크으으으은 상관은 없는데 2번은 'Ancient Toassian Tome'를 줍줍하고 꼭 책을 읽도록 합니다.

- 책 읽으면 'The Dead God' 퀘스트를 강제로 받게 되는데 이걸 수행하면서 받는 보상이 어마어마 합니다.

- 2번 비밀방에 들어가면 'Librarian' 미친놈이 있으니 꼭 데스 저항력 올리고 잡는걸 추천합니다.

  http://www.exiledkingdoms.com/wiki/index.php?title=Librarian

  스샷이 귀찮아서 안올리지만(위 URL 참조) 화염 -20, 빙결 -20, 전기 -30 이므로 고블린 왕 모가지 따고 얻은 전기속성 무기로 잡는게 추가데미지가 들어가서 찔끔 더 수월할 겁니다.

- 1번 비밀방 입니다.... 항상 말하지만 방심하지 마세요.... 골로갑니다.

  제가 알기로 저 관 주변에 다 스파이크가 있을 겁니다. 오른쪽은 안밟아 봐서 모르겠네요

※ 팁

   비밀방은 스크롤 쓰세요.. 안쓰면 정신건강에 해롭습니다.

   그리고 고스트는 죽여도 조금만 있으면 되살아나니 되돌아갈 피나 여력이 없다면 귀환 스크롤 써서 마을로 바로 가도록 합니다.

2) Hunting bugs!

- 자 이제 용병도 있겠다 이전에 못잡았던 고블린 왕이나 Librarian(Weak) 놈을 잡아도 됩니다.

- 그건 그렇고 Hunting bug를 시작하겠습니다.

- 'Sheryl' NPC가 무서워서 벌벌떠니 내가 대신 잡아 드리리다 하고 

  오른쪽 맵에 표시된 곳에 가면 알이 있습니다.

  3마리 미믹이 있는데 때려 잡고 둥지 누르고 다시 잡습니다.

  2번 반복하면 알이 터지는데 터지고 나서 다시 'Sheryl'에게 가면 됩니다.

- AWA가 2 이상이면 굳이 둥지 안터뜨려도 다른 선택지가 나오니 손쉽게 ㄱㄱ

- 보상은 시원찮지만 경험치를 주니...200xp면 업드려 절해야죠...

3) A Wild Mystery

- 'Nisor' 에게 퀘스트를 받습니다. 이런 겁쟁이들.. 

  근데 겁낼만 합니다... 드루이드가 쎄거든요..

- 오른쪽 맵에 표시된 곳에 가면 동굴로 갑니다.

- 사실 저기 안들려도 됩니다.. 그냥 스토리 진행을 위해 들리는 거니까요

- 가면 제일 안쪽에 'The Undermother' 이란 미믹의 어머니? 랑 이야기 합니다.

  더러운 벌레놈!! 죽어라!!! 하고 덤벼드는 선택지를 고르면 내가 골로가니 들어가기 전에 저장을 해놓던가

  아니면 앞서 말했듯이 대화 안해도 됩니다.

- 저런 동굴에 들어가면 오른쪽 그림처럼 'Luminescent Fungus' 란 버섯이 있다면, 줍줍합니다. 

  Gather ingredients의 마지막 줍줍템이니까요

  (사진 아래 날짜를 보면 알겠지만 왼쪽은 20일 6시, 오른쪽은 21시 4시 입니다... 즉, 저도 미믹있는 동굴에서 못줍고 다른 동굴에서 주웠다는 거죠)

  100% 있는게 아닙니다... 그저 운이지요

- 자 이제 드루이드 한테 쫒겨난 'Undermother'를 구원해주기 위해 'Varannari Druid'를 잡으러 갑니다.

- North Bluemist River 서쪽으로 'Rhoneis Plains'로 갑니다.

- 왼쪽 그림에 표시된 곳에 가면 던전이 있습니다. 오른쪽 그림처럼 제일 안쪽에 문이 있고 거기에 드루이드가 삽니다.

  드루이드 스펙은 여길 참조 http://www.exiledkingdoms.com/wiki/index.php?title=Varannari_Druid

- 문을 열면 6~7렙 쫄따구 3마리와 드루이드가 있습니다.

  (왼쪽 사진아래 시간을 보면 21일 2시네요... 네 위에서 말한 버섯은 여기서 주웠습니다.)

- 드루이드가 힐을 쓰기 때문에 한 두마리는 빠르게 조지고 시작하는게 좋습니다.

  쫄따구 거의 다 잡았는데 힐쓰면 빡치거든요....

  아 난 탱이 미친놈이다 싶으면 드루이드 부터 조지는게 제일 좋지만 저를 따라 왔다면 그럴일이 없기에...

- 화염데미지가 들어오기 때문에 화염저항을 올리고 시작하는 것도 좋습니다.

- 도저히 못잡겠으면 나중에 잡아도 됩니다. 성직자에게 좋은 'Amulet of Wilderness'를 주거든요 

  'Amulet of Wilderness'는 +6 마나 +8 데스저항 +14 독저항 입니다. +6 마나라니!!!

※ 팁

   드루이드를 잡기전에 중간에 거쳐가는 'Rhoneis (City)' 에서 'Captain Teara' 에게 'Coyote Hunt'를 받아가세요

   코요테 10마리를 잡아야 하므로 드루이드를 잡으러 다녀오면 10마리 이상은 무조건 잡게 됩니다.

- 이분이시네요.

- 'Coyote Hunt' 보상에 대해 잠깐 이야기 하자면

ㄱ) 약속했던 보상을 받을 경우

    - Steel Longsword 또는 Small Emerald 둘 중에 선택

    - 240xp

    - 명성 Rhoneis(City) +3

    - 명성 Ilmara +3

ㄴ) 약속했던 보상을 안받을 경우

    - Potion of Lesser Shielding

    - 240xp

    - 명성 Rhoneis(City) +8

    - 명성 Ilmara +5

- 전 보상을 안받았습니다. 어차피 보상을 받아도 일반템인데 명성은 쌓기가 쉽지 않거든요

- 보상을 안받으면 미약하지만 명성이 더 쌓이기 때문입니다. 하지만, 아직까지는 별 의미는 없습니다만...

  참고로 Three는 명성이 중요합니다. 정말 매우

  나중에 마을에서 주는 퀘스트가 따로있는데 이거 받을때 좋긴합니다만, 아직 그거 받아 보진 않았네요

여기까지 'North Bluemist River' 에서 받을 수 있는 퀘스트 3개를 해봤습니다.

다음편

다음편은 'Rhoneis(City)' 에서 받을 수 있는 다른 퀘스트인

- Shaking Bones 과

- Lannegar Valley(City) 에서 받은 Gather ingredients의 Red Orchid 습득 장소에 대해 쓰겠습니다.

- 이쯤되면 경험치 올리기가 그지같을텐데 500골드로 게임시간 6일동안 5%xp를 더 받는 방법을 알려드리겠습니다.

- 해골 12개를 안모았다면 얼른 모아오세요.....귀찮습니다.

- A safe bet 퀘스트가 있지만 지금 상태로는 깨기가 힘드니 이건 어느정도 레벨과 아이템이 충족되면 다시 돌아오겠습니다.

1. 그래프 표현과 정의

1) 그래프의 정의와 종류

- G(V, E)로 정점(Vertex)과 간선(Edge)의 집합으로 구성된 자료구조

- 속성에 따른 분류

  방향 그래프(directed graph) / 무향 그래프(undirected graph) / 가중치 그래프(weighted graph)

- 형태에 따른 분류

  다중 그래프(multigraph) : 정점들 간에 두 개 이상의 간선이 있을 수 있는 그래프

  단순 그래프(simple graph) : 정점간 최대 한 개의 간선만 있는 그래프

  트리 혹은 루트 없는 트리(unrooted tree) : 부모자식 관계가 없을 뿐 형태는 무향 그래프

  이분 그래프(bipartite graph) : 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에 간선을 갖는 그래프

- 두 가지 이상의 속성을 가질 수 있음

  방향 가중치 그래프 / 이분 가중치 그래프 / 사이클이 없는 방향 그래프(Directed Acyclic Graph : DAG) = 의존 그래프

2) 암시적 그래프 구조들

- 그래프 같은 형태를 갖는 구조가 아니라도 그래프를 통해서 표현하면 쉽게 해결할 수 있는 문제

  서로 의존 관계를 갖는 그래프에서 순서를 결정하는 위상 정렬, 의존 그래프는 사이클이 없음(DAG)

  그래프의 크기는 아주 큰데 실제로는 그 중 일부만 사용 : 15-퍼즐

  2^N

3) 그래프의 표현 방법

- 그래프는 트리에 비해 훨씬 정적인 용도로 사용

※ 정적? : 새로운 정점이나 간선을 추가, 삭제 하는 경우가 적은 것

  그래프는 정적이므로 구조의 변경이 어렵더라도 메모리를 적게 차지하는 방법으로 구현함

- 간선의 정보를 어떤 식으로 저장하느냐에 따라 두 가지로 나눔

  인접 리스트 표현(adjacency list) : 그래프의 각 정점마다 해당 정점에서 나가는 간서의 목록을 저장해서 그래프를 표현

vector<list<int>> adj;

  인접 행렬 표현(adjacency matrix) : 2차원 배열을 이용하여 간선의 정보를 저장

vector<vector<bool>> adj;
bool adj[v][v];

- 인접 리스트와 인접 행렬 비교

                     특정 간선을 찾기 위한 탐색 시간         공간

인접 리스트                      V * V                            V+E

인접 행렬                           1                              V * V

※ 벡터 생성자 : 테케 여러개 돌려야 하는 경우에 초기화를 따로 해줄 필요가 없어서 좋음

vector<int> a;
vector<vector<int>> b;

a = vector<int>(할당 갯수, 초기값);
b = vector<vector<int>>(26, vector<int>(26, 0));

2. DFS

1) DFS ?

- 탐색 알고리즘 중 하나

- 깊이 우선 탐색

- 시간복잡도

  인접리스트 : 정점의 수 V + 간선의 수 E = O(|V| + |E|)

  인접행렬    : 정점의 수 V * 정점의 수 V = O(|V|^2)

2) dfs의 예제

- 두 정점이 서로 연결되어 있는가 확인

- 연결된 부분집합의 개수 세기

- 위상정렬 : dfs가 종료될 때 저장, 결과를 뒤집으면 위상정렬

                문제를 풀때는 사이클이 생성될 가능성이 있는 그래프는 위상정렬된 결과가 사이클을 갖는지 확인해줘야 함.

예제. 문제 : DICTIONARY

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

1, 2) 문제를 읽고 이해하기 및 재정의

- 어떤 고대사전에 단어가 적혀있는데 순서가 그 시대의 사전순

- 단어 목록이 주어 질 때, 알파벳 간의 상대적 순서를 출력

- 단어의 수 : 1 <= n <= 1,000

- 각 단어의 길이 : 1 <= L <= 20

- 순서에 모순이 있다면 "INVALID HYPOTESIS" 출력

- 없다면 알파벳 순서를 출력

3) 계획 세우기

- 단어에서 알파벳 간의 순서도 즉, 그래프를 만듦

- dfs로 그래프를 돌면서 가장 깊이 들어가는 알파벳이 순서상으로 가장 뒤이므로

  dfs가 끝날때 마다 알파벳을 추가

4) 계획 검증하기

- 시간복잡도 : 1000개의 단어 입력 시간 + => 싱크맞추는거 없이 cin 쓰면 오래 걸리지만 시간 초과 나진 않을 것 같음

                   그래프 생성시간 +            => 모든 단어를 다 봐야하므로 NL

                   위상정렬 시간 +               => 각 알파벳을 한번씩만 방문하면 되므로 26

                   사이클 검사 시간              => 한 알파벳이 사이클을 생성하는지 확인해야 하므로 26 * 26

  => O(NL)

5, 6) 계획 수행하기 및 회고하기

- 처음에 예제출력 결과를 이해하지 못해서 "위상정렬된 알파벳 + 위상정렬에 사용되지 않은 알파벳" 을 출력함.

  => ogklh abcdefijmnpqrstuvwxyz 무조건 이런식으로만 출력해야 되는지 암.

- 알고보니 그럴필요 없이 그래프를 만들고 있는 알파벳 간의 순서만 정렬하면 됨.

  zyxwvutsrqp  o  nmji  gklh  fedcba  이렇게 그래프를 형성하고 있지 않은 단어들은 순서가 상관없음. ogklh만 순서가 맞으면 됨.

- 그래서 처음에는 그래프를 이루고 있는 알파벳들만 dfs 재귀를 돌림

- 나중에는 그래프를 이루고 있지 않은 알파벳들은 순서가 상관없으므로 모든 알파벳을 dfs 재귀 돌림

- 위상정렬 결과가 사이클을 가지는지 하나씩 확인해봐야 하나???? 으흠...

- dfs를 돌리면서 사이클을 가지는지 확인하기에는 이전 루트를 다 기억하면서 비교해야 하므로 으흠...

- 배열을 하나 만들어서 dfs가 끝나는 시점에 해당 정점이 끝났다는 표시를 해줌.

  방문은 했지만, 끝나지 않은 정점을 방문한 경우 역방향 간선 즉, 사이클

  bool check[n], end[n];

  void dfs(int c){

     check[c] = true;

     for(int i = 0; i < n; i++){

         if(!check[i])

              dfs(i);

         else if(!end[i])

              // cycle

     }

     end[c] = true;

     // 위상정렬 추가

  }

소스코드

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int t, n;
vector<char> ans;
vector<bool> check;
vector<vector<int> > graph;

int min(int a, int b){
	return ((a < b) ? a : b);
}

bool make_cycle(){
	for (int i = 0; i < (int)ans.size() - 1; i++)
		for (int j = i + 1; j < ans.size(); j++)
			if (graph[ans[i] - 'a'][ans[j] - 'a'])
				return true;
	return false;
}

void dfs(int node){
	check[node] = true;

	for (int i = 0; i < 26; i++)
		if (!check[i] && graph[node][i])
			dfs(i);

	ans.push_back((char)(node + 'a'));
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		vector<string> temp(n);
		// 정점의 갯수를 정확하게 알 수 없기에 알파벳 갯수인 26개로 잡음.
		graph = vector<vector<int> >(26, vector<int>(26, 0));
		check = vector<bool>(26, false);
		for (int i = 0; i < n; i++)
			cin >> temp[i];

		// make graph
		for (int i = 0; i < n - 1; i++)
			for (int j = 0; j < min(temp[i].size(), temp[i + 1].size()); j++)
				if (temp[i][j] != temp[i + 1][j]){
					graph[temp[i][j] - 'a'][temp[i + 1][j] - 'a'] = 1;
					break;
				}

		// make topolgotical sorting
		for (int i = 0; i < 26; i++)
			if (!check[i])
				dfs(i);

		// 위상정렬 결과에 사이클이 있는가?
		if (make_cycle()){
			cout << "INVALID HYPOTHESIS";
		}
		else{
			for (int i = ans.size(); i > 0; i--)
				cout << ans[i - 1];
		}
		cout << "\n";

		ans.clear();
	}
	return 0;
}

- 알고리즘 문제 해결전략 2편 중 -

- 저작권 문제시 삭제하겠습니다 -

문제출처 : https://www.acmicpc.net/problem/1325

1. 문제요약

- N개의 컴퓨터, 1 <= N <= 10,000

- M개의 신뢰관계, 1 <= M <= 100,000

- A가 B를 신뢰한다. => B를 해킹하면 A도 해킹할 수 있다. / A를 해킹하면 B는 해킹할 수 없다.

- M개의 A B 쌍이 주어지며, A가 B를 신뢰한다.

- 한 번에 가장 많은 컴퓨터를 해킹 할 수 있는 컴퓨터의 번호를 오름차순 출력

2. 접근방법

- 단뱡향 그래프

- 신뢰관계에 대해 int 더블배열을 쓰면 4 * 10,000 * 10,000 = 400,000,000byte = 400Mbyte로 메모리 초과

  => 더블 벡터로 입력 받음

- 하나의 컴퓨터에서 해킹 할 수 있는 모든 컴퓨터를 찾는다.

- 한 정점에서 시작하여 다시 그 정점을 방문하면 안되므로 체크 배열을 쓴다.

3. 시간복잡도

- 모든 정점의 갯수 N * 최대 쌍의 갯수 M = O(NM)

- NM = 10억 인데 5초 안에 들어오려나...3.8초 나옴

- SCC 라는 알고리즘을 쓰면 더 빨리 돌릴 수 있다는데 나중에 공부해야지

4. 회고

- 중간에 dp 처럼 아에 한번 방문한 정점은 다시는 방문하지 않아도 되지 않을까 해서 그렇게 했는데

  이렇게 하면 체크가 없어서 그래프가 싸이클을 만들면 무한루프로 빠져들어감......

  => 그래프에서는 싸이클을 생각해보자

- 한 정점(1 번)에서 시작해서 방문했던 정점을 재 방문 하는 경우(1 -> 2 -> 1)만 막아야지

  새로운 다른 정점(2 번)에서 시작해서 이전 정점에서 방문했던 정점(1 번에서 방문했던 정점들) 방문을 막으면 안됨

  쌍방 연결이나, 한 노드를 여러 노드가 방문할 수 있기 때문

  => 체크 배열 초기화 !!!!!!!

- 컴퓨터의 번호는 1 부터 시작하므로 배열의 크기는 n + 1 !!!!!!!!!

  for문 인덱스도 1 !!!!!!!

소스코드

#include<iostream>
#include<vector>
using namespace std;

int n, m;
int nodeNum[10001];
bool check[10001];
vector<vector<int> > tree;

int max(int a, int b){
	return ((a > b) ? a : b);
}

int dfs(int node){
	check[node] = true;

	int ret = 0;
	for (int i = 0; i < (int)tree[node].size(); i++)
		if (!check[tree[node][i]])
			ret += dfs(tree[node][i]) + 1;

	return ret;
}

int main(void){
	cin >> n >> m;
	tree.resize(n + 1);
	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		tree[b].push_back(a);
	}

	int maxV = 0;
	for (int i = 1; i <= n; i++){
		nodeNum[i] = dfs(i);
		maxV = max(maxV, nodeNum[i]);
		for (int j = 0; j <= n; j++)
			check[j] = false;
	}

	for (int i = 1; i <= n; i++)
		if (nodeNum[i] == maxV) cout << i << " ";
	cout << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]