<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
우선 입력에 따라 그래프를 제대로 구성했다면, BFS나 DFS를 사용하면 단지를 쉽게 찾을 수 있다. 이 중에서 나는 BFS를 사용했다.
그래프 연결
그래프 연결에 이차원 배열을 사용하지 않았다 왜냐하면 입력 한개를 row 하나라고 생각했을 때, 나는 인덱스를 사용하고 싶었는데 이차원 배열을 사용하면 상하 row와 연결이 쉽지 않다고 생각했기 때문이다. 위 예제의 0110100 0110101 을 보면 각 입력의 011부분이 연결돼야 하는데 row[0][1] -> row[1][1] 연결이 쉽지 않다고 생각해서 이다. (삼차원 벡터를 사용하면 가능하지도?)
오래걸렸던 이유
문제 자체는 쉬웠고 접근법도 빠르게 떠올랐으며 정답에 가까웠다. 문제는 위 입력을 구현하는 것이 첫번째 고비였다. 두번째는 문제를 잘 못 이해해서 시간이 오래 걸렸는데 이것은 게시판을 둘러보면서 문제를 잘 못 이해했다는 것을 발견했다. 집 한채만 있을 때는 단지가 아니라서 생각해서 출력을 하지 않도록 했는데 집 한채도 단지라고 판정짓고 출력해야 했던 것이다. 이 경우에는 자기자신을 가르키게 해서 사이클을 형성했고 이 경우 자기자신만 자신을 가르키기 때문에 해당 정점의 연결이 몇개 돼 있는지 보고 한 개라면 이 경우인 것을 이용했다. (다른 정점과 연결이 되면 무조건 연결이 2개 이상이다) 그 두가지를 해결하니 문제도 해결됐다.
이번에는 map이라는 2차원 배열과 벡터 2차원 배열을 사용했다. 우선 입력 자체는 map에 우선 입력 후 벡터 2차원 배열(그래프 연결)에 edge들을 연결하는 식으로 구현했다. 지금 생각해보니 map이 없어도 입력받은 값들의 이전 값들만 이용하여 연결 할 수 있을 것 같다. (왼쪽 배열 값과 위쪽 배열 값, 대각선 배열 값)
생각한 팁
그래프를 연결할 때, 다른 edge와 연결이 되더라도 자신이 1이라면 자기 자신과의 사이클을 형성하는 것이 편하다. 다른 edge와 연결이 안 된 경우와 자기 자신의 사이클을 형성하는 것을 분리해 버리면 예외처리가 너무 복잡해지는 것 같았다.
오래걸렸던 이유
문제 자체는 해결 방법을 빠르게 생각했다. 실제로 크게 어렵지 않은 문제이기도 하고 대부분 현한 그대로가 정답일 수 있다고 생각한다. 우선 결론부터 짓으면 c++에 아직 익숙치 않아 속도가 나지 않는다고 생각한다. 이것은 구현력이 부족하다고 할 수 있겠다. 디버깅을 하면서 다음과 같은 문제가 있었다.
벡터를 초기화할 때 이전 테스트 케이스의 벡터 크기가 남아있음.(초기화 문제)
가로와 세로 크기를 입력 받은 뒤 둘을 서로 바꿔 생각함 속도 향상을 위해서 한번에 꼼꼼하게 코딩하도록 하고 익숙치 않은 함수들에 익숙해 지려고 노력해야 겠다.
voidedgeConnect(int width,int height) { int idx = 0; int isLeftLand = 0; int isCurLand = 0; int isUpLand = 0; int isLeftDiagonalLand = 0; int isRightDiagonalLand = 0;
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"; }
}
intmain() { 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으로 초기화한다
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 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시간 반 이상 소요시간이 넘어가면 풀던 것도 멈추고 풀이 방식이 맞는지 찾아보도록 해야함
queue를 사용할때 반복문의 조건으로 q.size()를 사용했었는데 처음에 의도한 것은 반복문을 시작할 때 q.size()만큼만 돌도록 하는 것이었으나 q.size()를 사용하면 BFS를 돌면서 q의 크기가 바뀌게 되어서 의도한대로 실행되지 않았다. 그래서 qSize라는 int 변수로 q.size()값을 저장하고 사용했다.
메모리 초과가 발생했는데 알고보니 섬 번호를 Marking하는 부분을 BFS로 구현했었는데 그 때문인 것 같다. 찾아보니 BFS는 큐로 탐색할 노드들을 다 저장하는 특성 상 공간복잡도가 복잡하다. DFS와 BFS의 특성에 대해서는 생각을 깊게 안해보았는데, 정리하자면 다음과 같다.