집중력을 기르고싶어서 여러가지 방법 중 독서를 해볼려고 했는데

서울대학교 추천도서 중에서 무슨 책을 읽을까 고민하다 예전부터 읽어보고 싶었던 총균쇠를 읽기로 했다.

무슨 책인지 아예 배경지식이 없는 상태로 인류역사에 대한 책인지만 알고있는 상태로 읽기 시작했다.

하루에 50페이지씩 읽으려 노력했으며 약 2주에 걸쳐서 완독했다.

이 책을 읽으며 흥미로웠던 내용을 주로 정리해보려고한다.

지금까지 있었던 모든 인류 역사는 그렇게 흘러갈 수 밖에 없던 근본적인 이유가 존재한다

지금껏 생각해보지는 않았던 것이기도하고 본 책의 도입부에서 던진 질문이기도 한 어떤 민족이 타 민족을 정복하고 전쟁에서 승리하는 것에 대한 근본적인 원인은 무엇인가 하는 질문이 이 책에서 말하고자 하는 바를 가장 많이 담고있다.

이 책을 읽기 전에는 나는 그 원인이 자원, 인종적인 차이로 인해서 승리한 것이 아닐까 혹은 그런 이유가 존재하는가 우연으로 이루어진 것이 아닌가 생각했었지만 본 책을 읽고나서는 이가 잘못된 생각임을 알게됐다.

근본적인 이유는 환경 그리고 식량 생산이 근본적인 이유이다.

먼 과거 인간 사이의 전쟁에서 중요한 요인은 여러가지가 있지만 인구수도 중요한 요인이라고 할 수 있다.

그렇다면 어떤 그룹이 인구수를 빠르게 늘릴 수 있었을까

그것은 식량 생산을 먼저 시작한 종족이라고 저자는 말한다

우선 인류가 어느정도의 뇌 크기를 가지고 나서부터,

식량 생산을 먼저할 수 있게 되는 환경이 존재하는데 그

환경은 수렵채집에 너무 유리하지도 않고(수렵채집만 하고 정착을 하지 않을 수 있음)

처음에는 수렵채집으로 먹고살 수 있는 정도에 어느정도 환경을 파악하고 나서 식량생산에 유리한 환경(정착에 유리하게 사용할 수 있는 동식물이 풍부한)이 가장 정착을 하여 인구수를 늘리기에 적합하다는 것이다.

정착해서 식량 생산을 한 그 이후는?

정착하여 식량 생산을 시작하면 인구가 폭발적으로 증가한다

인구가 증가하고 관리할것이 많아지면 중앙집권 체제가 들어서게 되고

문명의 기술자, 엘리트들을 먹여살릴 수 있게 되면서 기술이나 문자를 만들게 된다.

또한 아무래도 땅이 넓을수록 인구가 많아지기 좋고 인구가 많으면 기술자가 그만큼 많아지기 좋다

또한 유라시아같이 가로축이 긴 나라가 큰 국가를 형성하기가 좋은데

식물이 생존할때 같은 적도일수록 생존하기가 좋기때문에 국가를 이루기에 좋기 때문이다.

균

정착을 하고 나서 동물을 가축화하고 나면 동물에서나 위생상에서 균에게 노출된다.

우선 균에 노출되고 나면 한번 해당 균이 휩쓴 뒤 그 지역에사는 사람들은 면역력을 가지게 된다.

이러한 면역력을 가진 사람들이 다른 지역에 가서 정복전쟁을 하게 되면 다른 지역에 사는 사람들은

면역력이 없기때문에 다시 그지역에서 균이 휩쓸기 마련이다.

요약

이렇게 인간이 다른 인간을 정복한 것은 단지 그 인종이 우월해서 라던가 운이 좋아서라던가 같은 이유가 아닌 주어진 환경에 의해 유리하게 출발한 인간이 다른 인간을 정복하기가 좋았다고 요약할 수 있다.

그 외에 천재발명가의 발생은 영향이 없냐는 흥미로운 질문을 할 수 있는데,

저자는 발명이라는 것은 발명가 한명에 의해서만 어떠한 발명이 이루어지는 것이 아니고

시대적,사회적으로 필요로하는 물건에 대해서 주로 이루어지기가 쉽다는 것이기 때문에

이 천재 발명가 조차도 환경,시대가 중요함을 알 수 있다.

또한 만약 천재 발명가가 없었다면 그 나라가 흥하거나 망하거나 하는것에 대한 측량은

너무나 결과론적이기 때문에 현실적으로는 힘들다는 것이다.

마지막으로 중국에 관한 얘기가 흥미로워 이를 정리하고 독후감을 마치려한다.

중국은 유라시아의 다양한 식생물, 가로축으로 넓은 땅덩어리 실제로 다른 대륙의 인간보다 빠르고 유리하게 시작한 국가인데, 왜 어느순간부터 유럽에 뒤쳐졌는가 하는 내용에 대한 설명이 흥미로웠다

이것은 지리적으로 중국은 어느 시점부터 매우 빠르게 통합된 국가인데

그에반해 유럽은 지리적으로 분열된 국가이다.

너무 통합된 국가이기 때문에 오히려 혁신성을 해친 것이 중국의 케이스이다.

중앙집권체제에서 모든걸 결정해버린다고 생각하면 기술같은 혁신에 있어서 한쪽에 치우치기 좋기 때문에 이러한 현상이 생겼다고 볼 수 있다.

후기

이렇게 단지 내가 흥미로웠던 내용을 중심으로 정리해보았다.

지식적인 측면, 논리적인 생각의 흐름에서 배움을 얻었다.

집중력도 처음 책을 읽을때는 5페이지 집중하기도 힘들었는데 읽다보니 집중력이 점차 느는것 같았다.

다음 책도 아마 서울대 추천도서중 고르지 않을까 생각하려고 한다.

이렇게 독후감을 마무리하려고 한다.

개요

백준 문제 2667번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 4시간

https://www.acmicpc.net/problem/2667

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다.
1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.
여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
대각선상에 집이 있는 경우는 연결된 것이 아니다.
<그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다.
지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력
1
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1
3
7
8
9

계획한 풀이법

우선 입력에 따라 그래프를 제대로 구성했다면, BFS나 DFS를 사용하면 단지를 쉽게 찾을 수 있다.
이 중에서 나는 BFS를 사용했다.

그래프 연결

그래프 연결에 이차원 배열을 사용하지 않았다 왜냐하면 입력 한개를 row 하나라고 생각했을 때,
나는 인덱스를 사용하고 싶었는데 이차원 배열을 사용하면 상하 row와 연결이 쉽지 않다고 생각했기 때문이다.
위 예제의
0110100
0110101
을 보면 각 입력의 011부분이 연결돼야 하는데 row[0][1] -> row[1][1]
연결이 쉽지 않다고 생각해서 이다. (삼차원 벡터를 사용하면 가능하지도?)

오래걸렸던 이유

문제 자체는 쉬웠고 접근법도 빠르게 떠올랐으며 정답에 가까웠다.
문제는 위 입력을 구현하는 것이 첫번째 고비였다.
두번째는 문제를 잘 못 이해해서 시간이 오래 걸렸는데
이것은 게시판을 둘러보면서 문제를 잘 못 이해했다는 것을 발견했다.
집 한채만 있을 때는 단지가 아니라서 생각해서 출력을 하지 않도록 했는데
집 한채도 단지라고 판정짓고 출력해야 했던 것이다.
이 경우에는 자기자신을 가르키게 해서 사이클을 형성했고 이 경우 자기자신만 자신을 가르키기 때문에
해당 정점의 연결이 몇개 돼 있는지 보고 한 개라면 이 경우인 것을 이용했다.
(다른 정점과 연결이 되면 무조건 연결이 2개 이상이다)
그 두가지를 해결하니 문제도 해결됐다.

코드

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
const int MAX = 1001;

struct
{
	int num;



}



void Graph::connectEdge(int v,int e)
{
	graph[v].push_back(e);
	if(v == e)
	{
		return;
	}
	graph[e].push_back(v);
}



void Graph:: BFS(int startV)
{
	queue<int> que;
	que.push(startV);
	int curV = 0;
	int notVisited = 1;
	int houseCount = 1;
	visit[startV] = true;

	if(graph[startV].size() == 1)
	{
		houseSet.push_back(houseCount);
		return;
	}
	while(que.size()!=0)
	{
		curV = que.front();
		que.pop();
		////cout << "현재 정점 : " << curV << "\n";
		for(int i=0;i<graph[curV].size();i++)
		{
			
			if(visit[graph[curV][i]] == 1)
			{
				continue;
			}

			notVisited = 0;
			que.push(graph[curV][i]);
			visit[graph[curV][i]] = true;

			houseCount++;
		}
	}

	if(!notVisited)
	{
		houseSet.push_back(houseCount);
		//doSomeThing(); 
	}

}


void solve()
{
	int n = 0;
	cin >> n;
	Graph g = Graph();
	fill_n(g.visit,MAX,0);
	int maxSize = n*n;
	int num[maxSize];
	for(int i=0;i<maxSize;i++)
	{
		vector<int> nodeTmp;
		g.graph.push_back(nodeTmp);
	}

	int idx = 0;

	for(int row = 0;row < n;row++)
	{
		char input[n];
		char prevRow[n];

		for(int cal = 0;cal<n;cal++,idx++)
		{
			cin >> input[cal];
			if(input[cal] - '0')
			{
				if(cal == 0)
				{
					g.connectEdge(idx,idx);
				}
				else if(input[cal-1] - '0')
				{
					g.connectEdge(idx,idx-1);
				}
				else
				{
					g.connectEdge(idx,idx);
				}
			}
			
			if(row != 0)
			{
				if(prevRow[cal]  - '0' && input[cal] - '0')
				{
					g.connectEdge(idx - n,idx);
				}

			}
		}

		for(int i=0;i<n;i++)
		{
			prevRow[i] = input[i];
		}

	}
	for(int i=0;i<maxSize;i++)
	{
		if(g.visit[i])
		{
			continue;
		}
		g.BFS(i);
	}
	cout << g.houseSet.size() <<"\n";
	sort(g.houseSet.begin(),g.houseSet.end());
	if(g.houseSet.size() == 0)
	{
		cout << "0";
	}
	for(int i=0;i<g.houseSet.size();i++)
	{
		cout << g.houseSet[i] << "\n";
	}

}

int main()
{
	solve();
}

개요

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

문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력
각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

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

예제 입력 1 
1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

1
2
3
4
5
6
7
8

예제 출력 1
0
1
1
3
1
9  

계획한 풀이법

• 그래프 연결(연결되지 않으면 자기자신만 연결)
• DFS로 개수 세기

그래프 연결

이번에는 map이라는 2차원 배열과 벡터 2차원 배열을 사용했다.
우선 입력 자체는 map에 우선 입력 후 벡터 2차원 배열(그래프 연결)에 edge들을 연결하는 식으로 구현했다.
지금 생각해보니 map이 없어도 입력받은 값들의 이전 값들만 이용하여 연결 할 수 있을 것 같다. (왼쪽 배열 값과 위쪽 배열 값, 대각선 배열 값)

생각한 팁

그래프를 연결할 때, 다른 edge와 연결이 되더라도 자신이 1이라면 자기 자신과의 사이클을 형성하는 것이 편하다.
다른 edge와 연결이 안 된 경우와 자기 자신의 사이클을 형성하는 것을 분리해 버리면 예외처리가 너무 복잡해지는 것 같았다.

오래걸렸던 이유

문제 자체는 해결 방법을 빠르게 생각했다.
실제로 크게 어렵지 않은 문제이기도 하고 대부분 현한 그대로가 정답일 수 있다고 생각한다.
우선 결론부터 짓으면 c++에 아직 익숙치 않아 속도가 나지 않는다고 생각한다.
이것은 구현력이 부족하다고 할 수 있겠다.
디버깅을 하면서 다음과 같은 문제가 있었다.

• 벡터를 초기화할 때 이전 테스트 케이스의 벡터 크기가 남아있음.(초기화 문제)
• 가로와 세로 크기를 입력 받은 뒤 둘을 서로 바꿔 생각함
  속도 향상을 위해서 한번에 꼼꼼하게 코딩하도록 하고 익숙치 않은 함수들에 익숙해 지려고 노력해야 겠다.

코드

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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAX = 2500;

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

//전역변수 써서 코드 간결하게 짜보기


void init(int row,int cal)
{	
    for(int i=0;i < graph.size();i++)
	{
		graph[i].clear();
	}
	graph.clear();
	int maxIdx = row * cal;
	for(int i = 0;i<row;i++)
	{
		for(int j= 0;j<cal;j++)
		{
			cin >> map[i][j];
		}
	}
	for(int i=0;i<maxIdx;i++)
	{
		vector<int> tmp;
		graph.push_back(tmp);
	}
}

void connectEdge(int v,int e)
{
	//////cout << "V와 E 연결\n";
	//////cout << v << " " << e <<"\n";
	graph[v].push_back(e);
	graph[e].push_back(v);
}

int DFS(int startV)
{
	int onesCheck = 0;
	stack <int> s;
	s.push(startV);
	int curV = 0;
	//cout << "시작 정점 : " << startV << "\n";
	while(s.size()!= 0)
	{
		curV = s.top();
		//cout << "V : " << curV << "\n";
		s.pop();
		
		visit[curV] = true;
		//cout << graph[curV].size() << "<- 크기\n";
		for(int i=0;i<graph[curV].size();i++)
		{
			if(!visit[graph[curV][i]])
			{
				s.push(graph[curV][i]);
			}			
			onesCheck = 1;
		}



	}	
	
	if(onesCheck)
	{
		return 1;
	}

	return 0;



}



void edgeConnect(int width,int height)
{
	int idx = 0;
	int isLeftLand = 0;
	int isCurLand = 0;
	int isUpLand = 0;
	int isLeftDiagonalLand = 0;
	int isRightDiagonalLand = 0;


	for(int row = 0; row < height; row++)
	{
		for(int cal = 0;cal < width; cal++,idx++)
		{
			isCurLand = map[row][cal];
			if(isCurLand)
			{
				//cout << idx << "번째 연결 시도\n";
				int isConnectedOnce = 0;
				if(cal-1 >= 0)
				{
					//왼쪽 연결
					isLeftLand = map[row][cal-1];
					if(isLeftLand)
					{
						//cout << "왼쪽 연결\n";
						connectEdge(idx,idx-1);
						isConnectedOnce = 1;
					}
				}
				if(row != 0)
				{
					//위 연결
					isUpLand = map[row-1][cal];
					if(isUpLand)
					{
						//cout << "위 연결\n";

						connectEdge(idx,idx-width);
						isConnectedOnce = 1;

					}

					//왼쪽 대각선 연결
					if(cal != 0)
					{
						isLeftDiagonalLand = map[row-1][cal-1];
						if(isLeftDiagonalLand)
						{
							//cout << "왼쪽 위 대각선 연결\n";

							connectEdge(idx,idx-1-width);
							isConnectedOnce = 1;

						}
					}

					//오른 대각선 연결
					if(cal+1 != width)
					{
						isRightDiagonalLand = map[row-1][cal+1];
						if(isRightDiagonalLand)
						{
							//cout << "오른 위 대각선 연결\n";
							connectEdge(idx,idx+1-width);
							isConnectedOnce = 1;

						}
					}
				}

				if(!isConnectedOnce)
				{
					//cout << "자기자신 연결\n";
					connectEdge(idx,idx);
				}

			}
		}
	}
}

void printAll(int height,int width)
{
	//cout << "프린트 시작 : \n";
	for(int row = 0;row<height;row++)
	{
		for(int cal = 0; cal<width;cal++)
		{
			//cout << map[row][cal] << " ";
		}
		//cout << "\n";
	}
	//cout << "프린트 종료\n";
}

void solve()
{
	int width = -1;
	int height = -1;
	int maxIdx = 0;
	int landCount = 0;
	int count = 0;
	while(1)
	{
		//cout << ++count << "번째 테스트케이스\n";
		landCount = 0;
		cin >> width >> height;
		//cout << width << " " << height << "\n";
		maxIdx = width * height;
		if(width == 0 && height == 0)
		{
			break;
		}
		
		fill_n(visit,MAX,0);
		fill(&map[0][0],&map[MAX-1][MAX],0);
		//벡터 해제 필요
		init(height,width);

		if(width == 1 && height == 1)
		{
			cout << map[0][0] << "\n";
			continue;
		}
		
		edgeConnect(width,height);
		for(int i = 0;i<maxIdx;i++)
		{
			if(!visit[i])
			{
				int result = 0;
				//cout << i << "번째 DFS 시작\n";
				result = DFS(i);
				if(result)
				{
					//cout << i << "번째 DFS의 탐색 성공\n";
				}
				landCount += result;

			}
		}
		cout << landCount << "\n";
	}



}

int main()
{
	solve();
}

익숙해져야 할 함수

• 2차원 벡터 초기화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

   //아래의 코드로 구현해서 테스트 케이스마다 벡터가 제대로 초기화 되지 않음
//MAX x MAX의 2차원 벡터 생성
vector<vector<int>> graph(MAX, vector<int>(MAX));
//앞의 두 인자는 어디부터 어디까지, 세번째 인자는 넣을 값
//begin부터 end까지 각 row에 MAX만큼의 각 vector<int>를 0으로 초기화한다 

fill(graph.begin(), graph.end(), vector<int>(MAX, 0));


//테스트 케이스마다 아래의 코드로 초기화 해주어야 했음.
for(int i=0;i <graph.size();i++)
{
	graph[i].clear();
}
graph.clear();

``

개요

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

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

​

계획한 풀이법

문제 해결을 위한 개괄적인 풀이방법은 단순하다.

• 익은 토마토라면 주변의 인접한 토마토를 보고 0이라면 그 토마토도 1로 바꾼다.
• 위 과정을 전체 토마트에 반복하며 날짜를 계산한다.
• 위 방법을 생각해보니 그래프가 필요한가? 싶어서 2차원 배열로 한번 풀어봤었다.
  • 2차원 배열로 풀이하니 시간 초과가 발생했다.

오래걸렸던 이유

• 그래프 연결 구현을 너무 복잡하게 구현하려고 함.
  • 복잡하기만 한 구현에 아무런 이점도 없는데도 그냥 고집으로 3차원 벡터를 사용할려고 함
• BFS를 쓰지 않고 구현
  • BFS를 안쓰고 구현할 수 있지 않을까? 하는 생각에 고집부리면서 BFS 안쓸려고함

속도 개선

• 고집을 부리느라 문제를 많이 못품
  • 문제 푼 수 = 경험 = 실력
• 1시간 반 이상 소요시간이 넘어가면 풀던 것도 멈추고 풀이 방식이 맞는지 찾아보도록 해야함
• 고집 부리지말고 가장 쉽고 빠르게 구현할 수 있는 방법을 사용하도록 하자

코드

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

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

const int MAX = 1001;
queue<pair<int,int>> q;
int graph[MAX][MAX];
int M = 0;
int N = 0;


bool leftCheck(int x,int y)
{
	if(x != 0 && graph[y][x-1] == 0)
	{
		return true;
	}
	return false;
}


bool rightCheck(int x,int y)
{
	if(x != N-1 && graph[y][x+1] == 0)
	{
		return true;
	}
	return false;

}


bool upCheck(int x,int y)
{
	if(y!=0 && graph[y-1][x] == 0)
	{
		return true;
	}
	return false;
}


bool downCheck(int x,int y)
{
	if(y+1 != M && graph[y+1][x] == 0)
	{
		return true;
	}
	return false;
}


void checkAndMark(int x,int y,int curDay)
{
	//cout << y+1 << " , " << x+1 << " : " << curDay << endl;
	if(leftCheck(x,y))
	{
		graph[y][x-1] = curDay+1;
		q.push(make_pair(y,x-1));
 	}
	if(rightCheck(x,y))
	{	
		graph[y][x+1] = curDay+1;
		q.push(make_pair(y,x+1));
	}
	if(upCheck(x,y))
	{	
		graph[y-1][x] = curDay+1;
		q.push(make_pair(y-1,x));
	}
	if(downCheck(x,y))
	{
		graph[y+1][x] = curDay+1;
		q.push(make_pair(y+1,x));
	}
}

void BFS()
{
	int curDay = 1;

	int x,y;

	while(q.size()!=0)
	{	
		y = q.front().first;
		x = q.front().second;
		q.pop();
		if(graph[y][x] == curDay)
		{
			checkAndMark(x,y,curDay);
		}
		else
		{
			curDay++;
			checkAndMark(x,y,curDay);
		}
	}
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			if(graph[i][j] == 0)
			{
				cout << -1;
				return;
			}
			//cout << graph[i][j] << " ";
		}
		//cout << "\n";

	}
	cout << curDay-1;

}

int main()
{
	//가로 = N
	//세로 = M
	cin >> N >> M;
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			cin >> graph[i][j];
			if(graph[i][j] == 1)
			{
				q.push(make_pair(i,j));

			}
		}
	}

	BFS();


}