침대 밖은 위험해!

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

1. 문제요약

- 케빈 베이컨 6단계 법칙 : 임의의 두 사람이 최소 몇 단계 만에 이어지는가

- 한 사람이 다른 모든 사람과 케빈 베이컨의 합이 최소인 사람을 출력

- 같은 사람이 있다면 번호가 작은 사람을 출력

2. 접근방법

- 한 사람이 다른사람까지 도달하는데 최소 단계

- 한 사람이 다른사람과의 케빈 베이컨을 하고

   n 명의 사람 전부다 해봄

3. 시간복잡도

- 최소 경로 찾기

  플로이드 => N^3

  bfs => VE

4. 회고

- 플로이드는 거리 초기값이 중요함

  최소 단계 합을 찾는 과정이 필요함

- bfs는 방문여부를 알아야 하므로 배열이 하나 더 필요함

  좀 더 깔끔하게 만들 수 있을거 같은데...

- dfs는 깊이 우선 탐색이므로 최단 거리가 나오면 갱신해줘야 함

소스코드 : 플로이드

#include<iostream>
using namespace std;

int n, m, f[101][101];

int main(void){
	cin >> n >> m;

	for (int i = 0; i < n + 1; i++)
		for (int j = 0; j < n + 1; j++)
			if (i == j) f[i][j] = 0;
			else f[i][j] = 987654321;

	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		f[a][b] = f[b][a] = 1;
	}

	for (int k = 1; k < n + 1; k++)
		for (int i = 1; i < n + 1; i++)
			for (int j = 1; j < n + 1; j++){
				if (i == j) continue; // 굳이 필요는 없음
				if (f[i][k] + f[k][j] < f[i][j])
					f[i][j] = f[j][i] = f[i][k] + f[k][j];
			}

	int min = 987654321, ans = 0;
	for (int i = 1; i < n + 1; i++){
		int temp = 0;
		for (int j = 1; j < n + 1; j++){
			temp += f[i][j];
		}
		if (temp < min){
			min = temp;
			ans = i;
		}
	}

	cout << ans << "\n";

	return 0;
}

소스코드 : bfs

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

int n, m, f[101][101], check[101][101];

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

	int min = 987654321, ans = 0;
	queue<int> q;
	for (int i = 1; i < n + 1; i++){
		q.push(i);
		check[i][i] = true;

		int temp = 0;
		while (!q.empty()){
			int now = q.front();
			q.pop();

			for (int j = 1; j < n + 1; j++){
				if (!check[i][j] && f[now][j] == 1){
					q.push(j);
					f[i][j] = f[i][now] + f[now][j];
					check[i][j] = true;
					temp += f[i][j];
				}
			}
		}

		if (temp < min){
			min = temp;
			ans = i;
		}
	}
	cout << ans << "\n";
	return 0;
}

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

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

1. 문제요약

- 집에서 편의점을 거져 목적지에 도달할 수 있는가?

- 1000m 이내의 다음 정점만 움직일 수 있음(맥주 20개, 개당 50m)

- 0 <= 편의점 개수, n <= 100

- -32768 <= 좌표 x, y <= 32767

2. 접근방법

- 경로가 있는지 찾는 문제 => 플로이드, 다익스트라

- 모든 정점을 다 방문해도 VE 이므로 시간 내에 들어올 것 같음 => bfs, dfs

※ 정점간 순서가 중요한 문제 : 위상정렬

   정점간 사이클이 중요한 문제 : 오일러 서킷

3. 시간복잡도

- 플로이드 워셜 : N^3

- bfs, dfs : N^2

  (한 정점당 다음 정점으로 가기 위해 살펴봐야 될 정점의 갯수 N * 정점의 갯수 N = N^2)

  (한 정점에서 간선의 수가 100개라고 한다면 총 간선의 수 100 * 100, VE는 최대 100 * 100 * 100)

  이 되겠지..? 여기선 간선의 수를 알 수 없으니

4. 회고

- 편의점간 1000m로

- bfs를 풀때 find를 왜넣었지 필요없네

소스코드 : 플로이드 워셜

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

int t, n;
vector<pair<int, int> > v;
vector<vector<int> > map;

int abs(int n){
	return ((n < 0) ? -n : n);
}

bool dist(int x1, int y1, int x2, int y2){
	return ((abs(x1 - x2) + abs(y1 - y2)) <= 1000 ? true : false);
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		v = vector<pair<int, int> >(n + 2, make_pair(0, 0));
		map = vector<vector<int> >(n + 2, vector<int>(n + 2, 0));

		for (int i = 0; i < n + 2; i++)
			cin >> v[i].first >> v[i].second;

		for (int i = 0; i < n + 2; i++)
			for (int j = 0; j < n + 2; j++)
				if (dist(v[i].first, v[i].second, v[j].first, v[j].second))
					map[i][j] = map[j][i] = 1;

		for (int k = 0; k < n + 2; k++)
			for (int i = 0; i < n + 1; i++)
				for (int j = 1; j < n + 2; j++)
					if (map[i][k] && map[k][j])
						map[i][j] = map[j][i] = 1;

		cout << (map[0][n + 1] ? "happy" : "sad") << "\n";
	}
	return 0;
}

소스코드 : bfs

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

int t, n;
vector<bool> check;
vector<pair<int, int> > v;

int abs(int x){
	return ((x < 0) ? -x : x);
}

bool dist(int x1, int y1, int x2, int y2){
	return ((abs(x1 - x2) + abs(y1 - y2)) <= 1000 ? true : false);
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		check = vector<bool>(n + 2, false);
		v = vector<pair<int, int> >(n + 2, make_pair(0, 0));
		for (int i = 0; i < n + 2; i++)
			cin >> v[i].first >> v[i].second;

		queue<int> q;
		q.push(0);
		check[0] = true;

		bool find = false;
		while (!q.empty()){
			int now = q.front();
			q.pop();

			if (v[now].first == v[n + 1].first && v[now].second == v[n + 1].second){
				find = true;
				break;
			}

			for (int i = 1; i < n + 2; i++){
				if (!check[i] && dist(v[now].first, v[now].second, v[i].first, v[i].second)){
					q.push(i);
					check[i] = true;
				}
			}
		}

		cout << (find ? "happy" : "sad") << "\n";
	}
	return 0;
}

소스코드 : dfs

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

int t, n;
vector<bool> check;
vector<pair<int, int> > v;

int abs(int x){
	return (x < 0 ? -x : x);
}

bool dist(int x1, int y1, int x2, int y2){
	return ((abs(x1 - x2) + abs(y1 - y2)) <= 1000 ? true : false);
}

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

	for (int i = 1; i < n + 2; i++)
		if (!check[i] && dist(v[now].first, v[now].second, v[i].first, v[i].second))
			dfs(i);
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		check = vector<bool>(n + 2, false);
		v = vector<pair<int, int> >(n + 2, make_pair(0, 0));

		for (int i = 0; i < n + 2; i++)
			cin >> v[i].first >> v[i].second;
		dfs(0);
		cout << (check[n + 1] ? "happy" : "sad") << "\n";
	}
	return 0;
}

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

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)에 있음]

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

1. 문제요약

- N*N 맵, 5 <= N <= 25

- 0 빈공간 / 1 집

- 상하좌우로 연결된 집을 하나의 단지

- 단지의 갯수와 각 단지별 집의 갯수를 오름차순으로 출력

2. 접근방법

- 방문한적이 없고, 집이면 방문해서 상하좌우로 연결된 모든집을 방문하여 단지를 만듬

- 단지를 만들면서 집의 갯수를 같이 셈

- bfs / dfs 모두 가능

3. 시간복잡도

- 모든 칸을 한번씩 방문하므로 N^2 = 625

4. 회고

- 전역변수를 안쓰고 리턴값을 쓰니까 조금 귀찮기는 한데 초기화를 안해도 되서 

- 나름의 장단점이 있는데 음...

- 방문한 집이면 맵 자체를 1 -> 0 으로 바꾸면 check 배열을 안써도 됨

- cin 만 쓰려니 공백없는 정수를 받을때는 불편함...

- sort 없이 1차원 배열을 최대 집 갯수 만큼 선언해서 단지 갯수를 입력함.

a[집 갯수] = 단지 갯수
for(int i = 0; i < n*n + 1; i++){
    for(int j = 0; j < a[i]; j++){
        cout << i << "\n";
    }
}

18.2.7

소스코드 수정 - num이 필요없잖아.. 벡터를 쓰는데

dfs만 수정함

소스코드 : dfs

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

int n;
vector<int> house;
char map[25][25];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int dfs(int row, int col){
	map[row][col] = '0';

	int ret = 1, nr, nc;
	for (int i = 0; i < 4; i++){
		nr = row + dx[i];
		nc = col + dy[i];

		if (0 <= nr && nr < n && 0 <= nc && nc < n && map[nr][nc] == '1')
			ret += dfs(nr, nc);
	}
	return ret;
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (map[i][j] == '1')
				house.push_back(dfs(i, j));

	sort(house.begin(), house.end());
	cout << house.size() << "\n";
	for (int i = 0; i < house.size(); i++)
		cout << house.at(i) << "\n";
	return 0;
}

소스코드 : bfs

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

int n, check[25][25];
char map[25][25];
vector<int> house;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	queue<pair<int, int>> q;
	
	int num = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			int cnt = 0;
			if (!check[i][j] && map[i][j] == '1'){
				q.push(make_pair(i, j));
				check[i][j] = true;
				num++; cnt++;

				while (!q.empty()){
					int x = q.front().first;
					int y = q.front().second;
					q.pop();

					int nx, ny;
					for (int k = 0; k < 4; k++){
						nx = x + dx[k];
						ny = y + dy[k];

						if (0 <= nx && nx < n && 0 <= ny && ny < n
							&& !check[nx][ny] && map[nx][ny] == '1'){
							check[nx][ny] = true;
							cnt++;
							q.push(make_pair(nx, ny));
						}
					}
				}
				house.push_back(cnt);
			}
		}
	}
	sort(house.begin(), house.end());
	cout << num << "\n";
	for (int i = 0; i < house.size(); i++)
		cout << house.at(i) << "\n";
}

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

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

1. 문제요약

- Tn = n(n+1)/2

- 자연수 K가 주어졌을 때 세개의 Tn 으로 나타낼 수 있으면 1, 없으면 0

- 3 <= K <= 1,000

2. 접근방법

- Tn이 몇개나 필요할까? => n(n+1)/2 <= 1,000 을 만족하는 n은 대충 44, 45

- T1 ~ T45 까지 3개를 뽑으면 되므로 45 * 45 * 45 = 91,125 이므로 1초 내에 들어옴

- 즉, 브루트 포스

- 여기서 45 * 45 * 45는 중복이 포함

- T1 + T1 + T2 / T1 + T2 + T1 / T2 + T1 + T1 은 같은 경우 이므로 제외 하면 조금 더 빨라 지겠지?

※ 실제로 다 해본 경우는 32ms / 중복 제외한 경우는 28ms

3. 시간복잡도

- N^3 = 91,125

4. 회고

- 미리 결과 합을 구해두면 출력에 편함

- 어차피 시간내에 들어오므로 굳이 안해도 됨

- 미리 구한 다른 사람은 0ms 인데 난 왜 28ms 이냐!!!

- 싱크 안맞춘 cin 때문인가.... T의 갯수가 몇개인지 모르니

- 미리 세개의 합을 구한 배열을 지역변수에서는 T45 + T45 + T45 = 3105 이상으로 잡아야 오버 인덱스 안남

  전역변수로 선언한다면 100 개 정도는 더 잡아주는 거 같음 3000개로도 통과되네

소스코드

#include<iostream>
using namespace std;

int main(void){
	int t, E[46] = { 0, 1 }, C[4000] = { 0 };
	cin >> t;

	for (int i = 2; i < 46; i++) E[i] = E[i - 1] + i;
	for (int i = 1; i < 46; i++)
		for (int j = i; j < 46; j++)
			for (int k = j; k < 46; k++)
				C[E[i] + E[j] + E[k]] = 1;

	while (t--){
		int n;
		cin >> n;
		cout << C[n] << "\n";
	}
	return 0;
}

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

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

1. 문제요약

- 어떤 자연수 M => 세 자릿수 라면 100a + 10b + c => M + a + b + c = N 즉, M과 각 자릿수의 합을 분해합, M을 생성자, N을 분해합

- 1 <= N <= 1,000,000 인 자연수 N이 주어 졌을 때 가장 작은 생성자는?

2. 접근방법

- 생성자는 분해합을 넘을 수 없으므로 1 부터 N-1 까지의 모든 수를 다 해보자

- 좀 더 생각해보면 분해합 N이 만들어 질 수 있는 생성자의 최대 자릿수는 6자릿수

  (생성자가 1,000,000 이면 분해합은 1,000,001 이므로 7 자릿수는 나올 수 없음)

  각 자릿수의 최대 값은 9

  즉, 생성자는 분해합 보다 54 이상 작을 수 없음.

  N-54 부터 N-1 까지만 찾으면 됨.

  가장 작은 수 부터 찾을 거니 처음 만나는 생성자가 최소값

3. 시간복잡도

- 두 가지 경우 모두 N

- 당연히 실제 시간은 전체 검색시 8ms / 55개 검사시 0ms

4. 회고

- 처음엔 다 했는데...

- 다른 사람의 소스 코드를 보고 깨달음

- 각 자릿수 합의 최대 범위

소스코드

#include<iostream>
using namespace std;

int main(void){
	int n;
	cin >> n;
	for (int i = n - 54; i < n; i++){
		int temp = i, sum = i;
		while (temp){
			sum += temp % 10;
			temp /= 10;
		}

		if (sum == n){
			cout << i << "\n";
			return 0;
		}
	}
	cout << '0' << "\n";
	return 0;
}

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

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

1. 문제요약

- 중요도에 따라 인쇄순서를 결정하고 특정 문서가 몇번째 출력되는가?

- 문서의 수 N <= 100, 0 <= 위치 M < N

2. 접근방법

- 일단 N이 얼마 안되기 때문에 브루트 포스

- 모든 문서가 큐에 저장

- 큐에 첫번째 문서가 출력 대상이 아니라면 뒤로 보냄

- 출력 대상이라면 출력

3. 시간복잡도

- Queue나 배열 하나만 쓴다면 N^3,

  출력 대상을 찾는데 하나의 문서와 모든 문서를 비교 해야 하므로 N^2, 

  모든 문서의 개수가 N 이므로 N^3

- Priority_Queue 라던가 가중치를 가지고 있다면,

  하나의 문서를 찾는데 N, 문서 전체의 개수가 N 이므로 N^2

4. 회고

- 배열을 큐처럼 만들어서 출력 대상이 아니면 배열 뒤에 붙이는 방식인 경우 최소 100 * 101 / 2 = 5050 이상 사이즈가 필요

- 인덱스만 가지고 움직인다면 배열 사이즈는 N이면 됨

  출력한 놈을 다시 출력하는 논리적 오류가 발생

  이런거 신경 안쓸려면 index를 출력한놈은 건너 뛰게 만들어야함

- 문서 번호와 문서 중요도를 보관해야 함

- 배열로 구현 했을 때 한칸씩 당기지 않으면 출력 했는지 안했는지 체크가 필요

- Queue 자료구조를 쓴다면 front를 뺄 때, 다른 자료와의 중요도를 비교할 수 있는 수단이 필요함

  하나씩 빼서 비교하던가 아니면 Priority_Queue나 중요도를 저장하고 있는 다른 배열과 비교가 필요

소스코드 : N^3

#include<iostream>
using namespace std;

int main(void){
	int t;
	cin >> t;
	while (t--){
		int n, m, q[101], check[101] = { 0 };
		cin >> n >> m;
		for (int i = 0; i < n; i++)
			cin >> q[i];

		int index = 0, cnt = 1;
		while (cnt <= n){
			if (index == n) index = 0;

			int i = 0;
			for (; i < n; i++){
				if (!check[i] && q[index] < q[i])
					break;
			}
			// !check[index]가 없다면 출력한 놈을 다시 출력하게 함
			// 예제에서 정답은 맞아도 중간 값이 틀림 => 결국은 틀림
			if (!check[index] && i == n){
				check[index] = cnt;
				cnt++;
			}

			index++;
		}

		cout << check[m] << "\n";
	}
	return 0;
}

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

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

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

해당편 퀘스트 순서

- The seed of trust : 보디가드

- Head Hunting : 고블린 왕 모가지 따기

0. 길가 상인, 길가 도둑, 창고만들기

- 길가 상인 1 - 무기, 기타 판매자

  : 날이 어두어 진 뒤에 길에 다니다 보면 이런 보따리 장사꾼을 만날 수 있는데 궁금하면 봐도 되고 아니면 그닥 필요는 없으니 넘겨도 됩니다.

- 길가 상인 2 - 가죽 구입자

  : 보따리 장사와 마찬가지로 날이 어두어졌을 때만 길에서 랜덤으로 만날 수 있습니다. 성직자로 새로 플레이하면서 한번 만났네요..

  : 초반에 돈을 왕창 벌 수 있는 아주 좋은 수단입니다.

  : 가죽은 다 팔지 말고 5장 정도는 남겨둡니다. 다음 퀘스트때 재료로 사용되므로 다시 구할려면 맵을 뛰어다는 귀찮은 일이 발생합니다.

- 길가 도둑

  : 길거리 상인과 마찬가지로 날이 어두어졌을 때만 만날 수 있습니다. 마찬가지로 랜덤이구요

  : 만나면 피가 엄청 없는 경우를 제외하고는 잡을 수 있으니 잡도록 합니다. 경험치와 템을 주니까요

  : 만약 잘 못 선택해서 싸워야 하는데 질거 같으면 마을로 도망갑니다. 마을 문지가가 다 죽여줍니다.

- 창고만들기

  : 아무 마을에서나 깃발 달린 집을 찾습니다.

  : 'Vault'를 누르면 4칸이 있는데 왼쪽 위칸을 누르면 '1000'gold에 개설 가능합니다. 

  : 초반 퀘스트와 잡템을 처분하면 1000gold 이상은 모이니 하나 정도는 뚫어둡니다.

  : 그래야 잡템들을 모아놓고 나중에 퀘스트 깰때 꺼내서 바로바로 클리어 가능합니다.

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

ㄹ) The seed of trust

- 보디가드 해주기 입니다.

- 마을에서 'Rodney'를 찾아서 보드가드를 해준다고 합니다.

- (오른쪽 그림처럼 'Journal'에서 확인 가능합니다.)

- 왼쪽 그림처럼 표시된 곧으로 가서 서쪽 맵으로 넘어 가도록 합니다.

- 거기서도 서쪽으로 계속 달리다 보면 오른쪽 맵처럼 작은 마을이 나오는데 거기까지 데려다 주면 됩니다.

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

- wiki를 꼭 참조하세요. 대답에 따라 약간이지만 보상이 달라집니다.

- 처음 이 게임 할 때 온갖 NPC 다 잡고 다녔더니 마을에 발도 못붙이는 상황이 벌어졌드랬죠........

ㅁ) Flesh is Weak + Forgotten Lore

- 좀비 가죽 모으기 입니다.

- 마을 'Three' 라는 교단자인 'Brother Janus' 에게 가서 퀘스트를 받으면 오른쪽 그림처럼 'zombie flesh'를 3개 가져오라고 합니다.

※ 팁 : 퀘스트를 받기 전에 'Three' 가 무엇이냐 라고 묻고 3개의 질문 목록이 나오는데 하나씩 다 하게 되면 '40xp'를 받을 수 있습니다.

- 왼쪽 그림처럼 퀘스트를 확인 합니다.

- 오른쪽 맵에서 남동 방향으로 보이는 검은색으로 가려진 돌들이 보이는데 그곳에 던전이 있습니다.

- 가시기 전에 이쯤 되면 3레벨 쯤 되고 돈도 조금 있을 텐데 방어구를 사서 아이템을 맞추고 가는 것을 추천 드립니다.

- 좀비가 3레벨 쯤이니 원활한 좀비 사냥과 다니다가 트랩 밟고 죽으면 스트레스가 폭발할테니까요

- 맵 입구에 가면 'Anton Gerdt' 이란 "Loreseeker'가 있습니다. 

- 아주 좋은 퀘스트 이므로 꼭 내가 자네 성물?? 3개를 찾아 주겠다고 하고 퀘스트를 수락 받습니다.

※ 팁 : 던전에서는 저장이 안되므로 꼭 들어가기 전에 저장을 해주고 들어가세요

         신나게 돌다가 죽으면 휴대폰을 던질지도 모릅니다.

- 트랩 입니다........ 알림창에 따르면 저거 밟았다고 피가 21이 날아 갔네요....

- 'Ydaya Tomb'의 전체 맵입니다.

- 왼쪽 위 1번과 오른쪽 상단 2번이 secret door 이므로 꼭 무조건 들어가시길 바랍니다.

- Flesh is Weak는 길에 다니는 좀비 죽이면 가죽 나오니 줍줍하면 되고

- Forgotten Lore는 위 맵에서 좌측 아래 3번 시체까지 가야만 하는데 몹이 좀 많습니다.

- 한마리 씩 잘 꿰어서 둘러싸이지 않고 잡도록 합니다.

※ 팁 : 몹이 여러마리가 달려오면 한번에 상대하기 벅차므로 문이나 좁은 골목을 이용하도록 합니다. 그러면 몹들이 한줄로 서게되고 뒤에 몹은 리치가 짧아 나한테 데미지를 줄 수 없기 때문에 한마리씩 상대가 가능합니다.

죽을거 같으면 던전 밖으로 나가면 '전투 중'이 없어지기 때문에 힐(2번 주어지는, 성직자 힐 제외) 사용이 가능합니다. 단, 몹이 문앞에 까지 따라 오므로 들어갔을때 몹이 문 앞에서 대기 타고 있습니다. 조심하세요

스켈레톤을 잡았을때 떨어지는 'Skull'은 12개가 될 때 까지 모아두세요. 다음 퀘스트에 필요합니다. 12개 이상은 필요없으니 팔아도 됩니다.

- 왼쪽사진은 '1번 secret door' 입니다.

- 오른쪽 사진은 '2번 secret door' 입니다.

※ 팁 : 워리어나 성직자는 저 문 찾는게 확률이 낮기 때문에 힘들겁니다. 그럼 마을 포션 상인한테 가면 'Scroll of Detection' 을 파는데 75% 확률로 비밀문이나 트랩을 찾아 줍니다. 한번에 성공한다는 보장이 없기 때문에 문 하나 찾는데 2장 정도 필요하니 4장 정도 챙겨 갑니다.

- 1번 비밀문은 그냥 뚫고 들어가서 잡으면 됩니다.

- 2번 비밀문 안에는 'Librarian(Weak)' 란 왠 미친 몬스터가 서식 중이니 만반의 준비가 필요합니다.

- 퀘스트를 받으면서 'Potion of Death Ward' 란 포션을 받았을 겁니다. 문열면 바로 달려나오기 때문에 미리 먹어두고 문을 열고 잡도록 합니다.

- 잘 보면 'Librarian(Weak)'의 'Resistances'가 화염, 빙결은 -25 / 번개는 -40 입니다. 이런 속성으로 때려 잡으면 데미지가 더 들어가기게 잡기 쉽습니다.

※ 팁 : 지금 깨기 힘들면 조금 나중으로 미뤄도 됩니다. 고블링 킹 모가지 따오면 번개 속성 무기를 주기에 그거 들고 잡으면 좀 더 수월 합니다.

- 잡았다고 방심하지 마세요. 트랩이 있습니다.

- 책 말고 시체 위로 가면 'shelf' 라는 책창이 있는데 꼭 먹으세요. 한 번밖에 못 먹기 때문에 두 번 들어갈 필요는 없습니다.

- 선반에서 총 4개의 아이템을 먹는데 바지는 좋으니까 입으면 되고 'Ancient Tolassian Tome' 이란 책을 얻는데 사용하면 스탯 1포인트 줍니다.

- 아주 좋습니다.

- 우선 좀비 가죽 3개를 모으면 Flesh is Weak 퀘스트는 성직자?인 'Brother Janus' 한테 가서 끝내면 됩니다.

- Forgotten Lore는 위에서 말한 3번 시체 까지 가야되는데 가면 책한권 줍습니다. 킹스브릿지까지 가야 깰 수 있으므로 일단 먹었으면 창고에 박아 둡니다.

- 이 던전에서 꼭 얻어야할 아이템들이 몇 개 있습니다.

- 첫 번째는 위에서 말한 Ancient Tolassian Tome 책이고

- 두 번째는 다음 퀘스트인 고블린 킹 모가지 따러 갈때 필요한 화염 저항력을 올려주는 반지를 두개 얻도록 합니다.(나중에 클리어할 생각이라면 2개 까지는 필요없습니다.)

   그럼 고블린을 잡으면서 얻은 +10 화염 저항 신발과 +10 화염 저항 링 두개면 총 30저항이 되는데 이래도 잡기는 힘듭니다.

- 세 번째는 루비 입니다. 돌다보면 루비 한두개 쯤은 나올텐데 창고에 박아두세요. 나중에 퀘스트 깰때 필요합니다. 없으면 구하기 엄청 귀찮거든요

   

   

- 저도 3번 도전해서 잡았네요... 퀘스트 남기고 가면 찝찝해서 잡았습니다.

※ 팁 : 고블린 왕 잡으면 모가지 주는데 팔지 말고 꼭 보관 해두세요. 나중에 필요합니다.

         고블린 왕 모가지는 게임내에서 딱 한번만 얻을 수 있고 만약 팔았다 하더라도 다른 아이템으로 대처 가능하지만 그거 구하러 다니기가 여간 귀찮은게 아닙니다. 주변 몬스터들도 얄짤없이 강하구요

※ 팁 : 이 팁을 안적고 갈뻔 했네요.

         인벤토리를 보면 우측 하단 돈 왼쪽으로 'Quick slots'가 있습니다. 모든 아이템이 가능합니다. 제 경우에는 1, 2번에는 hp, mp 포션을 3번에는 스왑무기를 셋팅하고 다녔네요

※ 참고 : Ancient Verses

- 도데체 그놈의 고블린 머리랑 루비 등등은 어디다가 쓰는가 싶은가 궁금할까봐 가져왔습니다.

- Ancient Verses라는 퀘스트 인데

- 2 Rubies, 1 Merple, Head of Itharrak the Firedancer(고블린 왕 머리), 1 Damaged Wolf Pelt를 차례대로 쥐어줘야 합니다.

- 마지막으로 나이트 워커를 잡으면 'Sonnet' 이라는 유니크 템을 주는데 +2 Armor와 기본 3-8 데미지, +5 성령?? 데미지인데 공속도 12로 아주 좋습니다.(단, 워리어와 로그 전용입니다.)

다음편

Northern Bluemist River

- A Warrior's Honor : 워리어 용병과 유니크 반지를 얻을 수 있음

- Hunting bugs! : 벌래 퇴치

- A Wild Mystery : 벌래 퇴치 2

아이템 속성 설명