Posted Updated algorithm4 minutes read (About 576 words)

Graph B2146

개요

백준 문제 2146번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 3시간
https://www.acmicpc.net/problem/2146

문제

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다.

색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

계획한 풀이법

풀이 방법)

  • 번호를 메겨 섬을 체크
  • 각 섬마다 BFS를 해가며 가장 짧은 거리의 다리를 찾는다

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 100;
const int INF = 987654321;
int mapSize = 0;
int map[MAX][MAX];
bool visit[MAX][MAX];

//왼 오 상 하
int check[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
//섬 마킹


void DFSMarking(int x, int y, int cnt)
{
        visit[y][x] = true;
        map[y][x] = cnt;
        for (int i = 0; i < 4; i++)
        {
                 int nextY = y + check[i][0];
                 int nextX = x + check[i][1];
                 if (0 <= nextY && nextY < mapSize && 0 <= nextX && nextX < mapSize)
                         if (map[nextY][nextX] && !visit[nextY][nextX])
                                 DFSMarking(nextX, nextY, cnt);
        }
}




void BFSMarking2(int startX,int startY,int numberOfLand)
{
	queue<pair<int,int>> q;
	q.push(make_pair(startX,startY));

	int nextX = 0;
	int nextY = 0;
	visit[startY][startX] = 1;
	map[startY][startX] = numberOfLand;
	
	while(q.size()!=0)
	{
		startX = q.front().first;
		startY = q.front().second;
		q.pop();
		map[startY][startX] = numberOfLand;
		visit[startY][startX] = 1;
		
		for(int i=0;i<4;i++)
		{
			nextY = startY + check[i][0];
			nextX = startX + check[i][1];
			if((nextX >= 0 && nextX <mapSize) && (nextY >= 0 && nextY <mapSize))
			{
				if(!visit[nextY][nextX] && map[nextY][nextX])
				{
					q.push(make_pair(nextX,nextY));
				}
			}
			
		}
	}

}

int BFS(int land)
{
	int count = 0;
	queue<pair<int,int>> q;
	int nextX,nextY,startX,startY;

	for(int i=0;i<mapSize;i++)
	{
		for(int j=0;j<mapSize;j++)
		{
			if(map[i][j] == land)
			{
				q.push(make_pair(j,i));
				//cout << "값 : " << map[i][j] << " land : " << land << "\n";
				//cout << i << " " << j << "pair 추가\n";
				visit[i][j] = 1;
			}
		}
	}	


	int qSize = 0;
	while(q.size() != 0)
	{
		qSize = q.size();
		for(int k=0;k<qSize;k++)
		{

			startX = q.front().first;
			startY = q.front().second;
			q.pop();
			for(int i=0;i<4;i++)
			{
				nextX = startX + check[i][1];
				nextY = startY + check[i][0];
				if((nextX >= 0 && nextX < mapSize) && (nextY >= 0 && nextY < mapSize))
				{
					
					if(map[nextY][nextX] && map[nextY][nextX] != land)
					{
						return count;
					}
					else if(!(map[nextY][nextX]) && !(visit[nextY][nextX]))
					{
						visit[nextY][nextX] = 1;
						q.push(make_pair(nextX,nextY));
					}
				}
			}
		}
		count++;
	} 




}

void init()
{
	cin >> mapSize;
	for(int i=0;i<mapSize;i++)
	{
		for(int j=0;j<mapSize;j++)
		{
			visit[i][j] = false;
			cin >> map[i][j];
		}
	}
}

void solve()
{
	init();
	int curX,curY,numberOfLand = 1,result = INF;

	for(int i=0;i<mapSize;i++)
	{
		for(int j=0;j<mapSize;j++)
		{
			if(!visit[i][j] && map[i][j])
			{
				DFSMarking(j,i,numberOfLand);
				numberOfLand++;
			}

		}
	}


	for(int land=1; land<numberOfLand;land++)
	{
		fill(&visit[0][0], &visit[MAX-1][MAX] ,0);
		result = min(result,BFS(land));
	}
	cout << result;
}

int main()
{
	solve();

}




막혔던 점

  1. queue를 사용할때 반복문의 조건으로 q.size()를 사용했었는데
    처음에 의도한 것은 반복문을 시작할 때 q.size()만큼만 돌도록 하는 것이었으나
    q.size()를 사용하면 BFS를 돌면서 q의 크기가 바뀌게 되어서 의도한대로 실행되지 않았다.
    그래서 qSize라는 int 변수로 q.size()값을 저장하고 사용했다.

  2. 메모리 초과가 발생했는데 알고보니 섬 번호를 Marking하는 부분을 BFS로 구현했었는데
    그 때문인 것 같다.
    찾아보니 BFS는 큐로 탐색할 노드들을 다 저장하는 특성 상 공간복잡도가 복잡하다.
    DFS와 BFS의 특성에 대해서는 생각을 깊게 안해보았는데, 정리하자면 다음과 같다.

    BFS: 최단경로를 찾는데 유리하다(각 시도마다 여러 경로로 뻗어나가는 모양)

    DFS: 찾아야 하는 노드가 깊다면 유리하다(한번에 깊게 들어가는 모양)

느낀 점

  • 이번 문제는 너무 코드 참조를 빠르게 한 것 같다(한시간 정도는 고민을 스스로 해야..)
Posted Updated algorithm3 minutes read (About 464 words)

Graph B1167

개요

백준 문제 1167번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 2시간
https://www.acmicpc.net/problem/1167

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

계획한 풀이법

처음엔 간단히 생각해서 그냥 입력받은 뒤 DFS하면 될 줄 알았지만
그렇지 않았다 왜냐하면 DFS는 가장 깊게 들어가게 되는데, 이 때 끝점과 시작점까지의 길이가 가장 긴 길이라고는 단정할 수 없다.
가중치는 가장 큰 값인 것이 분명하지만, 그것과 별개로 현재 시작점과 가중치가 가장 큰 정점이 가장 길지 않는 경우도 있기 때문이다.
그렇다면 가중치가 가장 높은 정점에서 DFS를 하게 되면 이때는 가중치가 가장 큰 정점이 시작점이니 여기서도 가장 큰 길이가 나오게 된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>

using namespace std;
const int MAX = 100001;

vector<pair<int, int> > graph[MAX];
bool visit[MAX];
int maxCost = 0;
int maxCostNode = 0;

int DFS(int startV,int cost)
{
	if(visit[startV])
	{
		return -1;
	}
	int result;
	visit[startV] = true;

	for(int i=0;i<graph[startV].size();i++)
	{	
		result = DFS(graph[startV][i].first,graph[startV][i].second+cost);
		if(result > maxCost)
		{
			maxCost = result;
			maxCostNode = graph[startV][i].first;
		}
	}
	return cost;

}

void connectEdge(int v,int e,int length)
{
	graph[v].push_back(make_pair(e,length));
}

void solve()
{

	int N = 0;
	cin >> N;

	int v = 0,e = 0,len = 0;
	for(int i=0;i<N;i++)
	{
		v = 0,e = 0,len = 0;
		cin >> v >> e;

		while(e != -1)
		{
			cin >> len;
			connectEdge(v,e,len);
			cin >> e;
			
		}
	}

	fill_n(visit,MAX,false);

	for(int i=1;i<=N;i++)
	{
		DFS(i,0);
	}
	maxCost = 0;
	fill_n(visit,MAX,false);
	DFS(maxCostNode,0);


	cout << maxCost;

}

int main()
{
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	solve();

}


느낀 점

  • 이 문제는 다른 사람의 풀이를 참조하고 이해하여 문제를 풀었다.
  • 문제를 읽고 떠오른 방법에 대한 검증을 깊게 해보자(너무 단순하게 생각하지 말자)
Posted Updated algorithm2 minutes read (About 360 words)

Graph B11725

개요

백준 문제 11725번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 35분
https://www.acmicpc.net/problem/11725

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

계획한 풀이법

문제를 보고 루트 없는 트리가 주어진다길래 무슨 말인가 했는데
루트를 1이라고 생각하고 입력이 주어진다는 말이었다.
풀이는 어쨌거나 트리는 최상위 루트가 존재해야하는데 그것이 1로 주어진다고 하여서 이를 힌트로 삼았다.
기준을 1로(시작점) 잡으면 그 이후 부터는 BFS로 이동하기 전 노드가 이동하려는 노드의 부모 노드가 되니 이를 마킹하면 되는 문제이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//PM 6:17
// 구상~ 
//PM 6:34
// 구현~
//PM 6:55
//완

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 100001;

vector<int> graph[MAX];
int visit[MAX];
int N;

void init()
{
	cin >> N;
	for(int i=0;i<N+1;i++)
	{
		visit[i] = 0;
	}
}

void edgeBiConnect(int v,int e)
{
	graph[v].push_back(e);
	graph[e].push_back(v);


}
//루트가 있을때 root -> e
void edgeOneConnect(int v)
{
	graph[1].push_back(v);
}

void BFS(int startV)
{
	queue<int> q;
	int curV;


	for(int i=0;i<graph[1].size();i++)
	{
		q.push(graph[1][i]);
		visit[graph[1][i]] = 1;
	}

	while(q.size() != 0)
	{
		curV = q.front();
		q.pop();

		for(int i=0;i<graph[curV].size();i++)
		{

			if(visit[graph[curV][i]] == 0)
			{
				q.push(graph[curV][i]);
				visit[graph[curV][i]] = curV;
			}
			
		}
	}


}

void solve()
{
	int v,e;
	for(int i=0;i<N;i++)
	{
		cin >> v >> e;
		if(v == 1)
		{
			edgeOneConnect(e);
		}
		else if(e == 1)
		{
			edgeOneConnect(v);
		}
		else
		{
			edgeBiConnect(v,e);
		}
	}
	BFS(1);
	for(int i=2;i<=N;i++)
	{
		cout << visit[i] << "\n";
	}
}


int main()
{
	init();
	solve();

}




느낀 점

  • 문제 자체는 쉬웠으나 한번에 고민한 것이 맞았고 코드도 나름 간결하게 짠 것 같아 만족한 풀이
Posted Updated algorithm2 minutes read (About 363 words)

Graph B1991

개요

백준 문제 1991번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 1시간
https://www.acmicpc.net/problem/1991

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

계획한 풀이법

풀이 방법)

  • 트리 생성
  • 전위,중위,후위 순회를 재귀로 구현

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>

using namespace std;

int tree[26][2];

void init()
{
	int n = 0;
	char rootVal,leftVal,rightVal;
	cin >> n;
	for(int i=0;i<n;i++)
	{
		cin >> rootVal >> leftVal >> rightVal;
		tree[rootVal-'A'][0] = leftVal;	
		tree[rootVal-'A'][1] = rightVal;
	}
}

void preOrder(char root)
{
	if(root == '.')
	{
		return;
	}
	cout << root;
	preOrder(tree[root-'A'][0]);
	preOrder(tree[root-'A'][1]);
}

void inOrder(char root)
{
	if(root == '.')
	{
		return;
	}
	inOrder(tree[root-'A'][0]);
	cout << root;
	inOrder(tree[root-'A'][1]);
}

void postOrder(char root)
{
	if(root == '.')
	{
		return;
	}
	postOrder(tree[root-'A'][0]);
	postOrder(tree[root-'A'][1]);
	cout << root;
}


void solve()
{
	preOrder('A');
	cout << "\n";
	inOrder('A');
	cout << "\n";
	postOrder('A');


}

int main()
{
	init();
	solve();

}



막혔던 점

  1. 위 코드는 다른사람의 코드를 보고나니 내 코드가 너무 안쓰러워서 다시 수정한 코드이다.
    연결리스트로 구현을 할려고 했는데, 입력을 한줄 씩 받으면서 재귀로 트리를 구성할려고 하니 N만큼 입력받는게
    전역함수를 추가하는 등 코드가 더러웠는데 역시 많이 상황에서 배열이 간단한 코드를 구성하는데 도움이 되는 것 같다.

느낀 점

  • 코드를 쉽게 짜려는 것에 중점을 두자
Follow

Categories

Recents

Archives

Tags

CRF3
algorithm72
book_report2
database1
java26
jpa1
pet project12
pet_project1
retrospect1
springboot3
web3
web pet project2
write3

Subscribe for updates

×