개요

백준3482: Labyrinth

• 입력
  The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers C and R (3 <= C,R <= 1000) indicating the number of columns and rows. Then exactly R lines follow, each containing C characters. These characters specify the labyrinth. Each of them is either a hash mark (#) or a period (.). Hash marks represent rocks, periods are free blocks. It is possible to walk between neighbouring blocks only, where neighbouring blocks are blocks sharing a common side. We cannot walk diagonally and we cannot step out of the labyrinth.

  The labyrinth is designed in such a way that there is exactly one path between any two free blocks. Consequently, if we find the proper hooks to connect, it is easy to find the right path connecting them.

• 출력
  Your program must print exactly one line of output for each test case. The line must contain the sentence "Maximum rope length is X." where X is the length of the longest path between any two free blocks, measured in blocks.

접근 방식

1. 처음에 해석을 잘 못했다. 제일 긴 거리를 찾는건 알겠는데
   트리형태라고 명시되어 있는걸 분석을 못했다.

2. 모든 두개의 블록을 잇는 루트는 정확히 하나만 있다.
   "The labyrinth is designed in such a way that there is exactly one path between any two free blocks."
   따라서 DFS방식을 통해 노드사이의 제일 긴 거리를 찾으려했다.

3. 결국 백준 1967번: 트리의 지름 문제와 같다.
   테케를 여러개 받는 트리의 지름 문제다.

4. 따라서 백준 1967번: 트리의 지름 문제와 동일하게
   각 노드에서 DFS방식으로 진행하며 해당 노드에서 갈수 있는 노드 중
   제일 긴 거리를 반환하는 int findLongestDiameter(int x,int y);
   함수를 구현하였다.
   해당 함수 내부에서 각 재귀마다 갈수있는 루트중 제일 긴 루트와 두번째로 긴 루트를 더해서 트리의 지름을 갱신하는 식으로 구현하였다.

   //(x,y)에서 안 가본 루트 중에 제일 긴 루트의 길이를 반환
   int findLongestDiameter(int x,int y) {
   	//방문했다면 0을 return
   	if (visited[x][y]) return 0;
   	visited[x][y] = true;
   	//x,y에서 갈수 있는 루트중에 제일 긴값과 두번째로 긴값
   	int tmpLongest = 0, tmpSecondLongest = 0;
   	//상하좌우만 갈수있고 대각선은 못간다고 문제에서 못 박았다.
   	for (int i = 0; i < 4; i++) {
   		int nextX = x + dx[i];
   		int nextY = y + dy[i];
   		//x,y에서 nextX,nextY 까지 길이는 1이므로 1더해줌
   		int tmp = 1;
   
   		//다음 좌표가 벽이면 컨티뉴
   		if (v[nextX][nextY] == '#')continue;
   		//다음좌표가 범위를 넘어가면 컨티뉴
   		if (nextX < 0 || nextY < 0 || nextX >= tmpRow || nextY >= tmpColumn) continue;
   		//이미 방문한 좌표라면 컨티뉴
   		if (visited[nextX][nextY]) continue;
   		//nextX,nextY값에서 시작한 루트중에 제일 긴 거리값을 반환해서 tmp에 더해줌 
   		tmp += findLongestDiameter(nextX, nextY);
   		//이번 tmp값이 제일 길다면 
   		if (tmp > tmpLongest) {
   			//두번째로긴값에 제일 긴값 저장해주고
   			tmpSecondLongest = tmpLongest;
   			//제일 긴값 갱신
   			tmpLongest = tmp;
   		}
   		//이번 tmp값이 두번째로 길다면 
   		else if(tmp<=tmpLongest&& tmp>tmpSecondLongest) 
   		{
   			//두번째로 긴값으로 갱신
   			tmpSecondLongest = tmp;
   		}
   	}
   	
   	//각 노드(x,y)에서 제일 긴값과 두번째로 긴값 갱신해서 답냄.
   	maxRopeLen = max(maxRopeLen, tmpSecondLongest+tmpLongest );
   	return tmpLongest;
   }

5. 해당 트리의 아무노드에서 실행해도 결국 전역변수로 선언한
   maxRopeLen에 답이 저장되므로 각 테케마다
   maxRopeLen을 출력하도록 구현하였다.

전체코드

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

//블록 정보값 #이랑 .입력용
char v[1001][1001];
//DFS방식으로 탐색하기 위함
bool visited[1001][1001];
//순서대로 총 테케 수, 행값, 열값, 시작 노드의 좌표X,Y, 제일 긴 로프 길이 저장용 변수
int N,tmpRow,tmpColumn,startX,startY,maxRopeLen;
//상하좌우값 표시 용이하도록
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

//초기화하는 함수
void Init() {
	fill(&v[0][0], &v[tmpRow][tmpColumn], 'a');
	fill(&visited[0][0], &visited[tmpRow][tmpColumn], false);
	maxRopeLen = 0;
}

void Solution();

void Input() {
	char tmpBlockInfo=' ';
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmpColumn >> tmpRow;
		Init();
		for (int i = 0; i < tmpRow; i++) {
			for (int j = 0; j < tmpColumn; j++) {
				cin >> tmpBlockInfo;
				//free 블록이라면 startX에 저장
				if (tmpBlockInfo == '.') {
					startX = i;
					startY = j;
				}
				v[i][j] = tmpBlockInfo;
			}
		}
		Solution();
	}
}
//블록에서 블록까지 이어진 길은 무조건 하나이므로 백트래킹방식이 아님, dfs로 찾기
//-> 1번노드부터 4번노드까지 1.2.3.4 이렇게 이어졌다면 1.2.5.4 이렇게 다른방식으로 4갈순없다는 뜻


//(x,y)에서 안 가본 루트 중에 제일 긴 루트의 길이를 반환
int findLongestDiameter(int x,int y) {
	//방문했다면 0을 return
	if (visited[x][y]) return 0;
	visited[x][y] = true;
	//x,y에서 갈수 있는 루트중에 제일 긴값과 두번째로 긴값
	int tmpLongest = 0, tmpSecondLongest = 0;
	//상하좌우만 갈수있고 대각선은 못간다고 문제에서 못 박았다.
	for (int i = 0; i < 4; i++) {
		int nextX = x + dx[i];
		int nextY = y + dy[i];
		//x,y에서 nextX,nextY 까지 길이는 1이므로 1더해줌
		int tmp = 1;

		//다음 좌표가 벽이면 컨티뉴
		if (v[nextX][nextY] == '#')continue;
		//다음좌표가 범위를 넘어가면 컨티뉴
		if (nextX < 0 || nextY < 0 || nextX >= tmpRow || nextY >= tmpColumn) continue;
		//이미 방문한 좌표라면 컨티뉴
		if (visited[nextX][nextY]) continue;
		//nextX,nextY값에서 시작한 루트중에 제일 긴 거리값을 반환해서 tmp에 더해줌 
		tmp += findLongestDiameter(nextX, nextY);
		//이번 tmp값이 제일 길다면 
		if (tmp > tmpLongest) {
			//두번째로긴값에 제일 긴값 저장해주고
			tmpSecondLongest = tmpLongest;
			//제일 긴값 갱신
			tmpLongest = tmp;
		}
		//이번 tmp값이 두번째로 길다면 
		else if(tmp<=tmpLongest&& tmp>tmpSecondLongest) 
		{
			//두번째로 긴값으로 갱신
			tmpSecondLongest = tmp;
		}
	}
	
	//각 노드(x,y)에서 제일 긴값과 두번째로 긴값 갱신해서 답냄.
	maxRopeLen = max(maxRopeLen, tmpSecondLongest+tmpLongest );
	return tmpLongest;
}

void Solution() {
	findLongestDiameter(startX, startY);
	cout <<"Maximum rope length is " << maxRopeLen<<"." << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	Input();
}

문풀후생

트리의 지름 문제와 똑같이 구현했는데 틀렸습니다가 떠서
정말 오래 고민을 한 문제다.

결론부터 말하면 초기화를 제대로 안해서 생긴 문제로
방문여부벡터와 블록 정보값 벡터는 초기화 했지만
maxRopeLen을 초기화를 안해줬더니
두번째 테케의 답이 첫번째 테케 답보다 작으면 첫번째 테케가 답으로
출력되는 사태가 벌어졌다..

예제도 첫번째 테케 답이 0으로 더 작은 케이스라 정말 이거하나로 며칠을 고민했다..
시간낭비는 엄청 했지만 덕분에 앞으론 더욱 신경쓰게 될것같다. ..