기본적으로 이 문제는 두가지 방법으로 구할 수 있다.
1) 일단 L의 위치들을 다른곳에 각자 구한뒤 위치 차이 중 최대값으로 구할 것이냐
2) 각위치에서 가장 멀리 떨어져있는 애들의 위치 중 최대값으로 구할 것이냐
금번엔 2번으로 구했지만 1번으로 구해보고 싶음.
#include<stdio.h>
#include<memory.h>
/*
5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW
*/
char map[50][50];
int visited[50][50] = { 0 };
int max = 0;
int distance = 0;
int N, M;
typedef struct {
int row;
int col;
} _position;
_position point[2500];
int Dy[4] = { -1, 0, 1, 0 };
int Dx[4] = { 0, -1, 0, 1 };
int bfs(int row, int col)
{
int head, tail;
int max;
int i;
int tmp_row, tmp_col;
max = -1;
head = 0;
tail = 0;
memset(visited, -1, sizeof(visited)); // memory.h 나 string.h 를 못쓸때는 강제for문으로 변경해줘야함
memset(point, -1, sizeof(point)); // memory.h 나 string.h 를 못쓸때는 강제for문으로 변경해줘야함
point[tail].row = row;
point[tail].col = col;
visited[row][col] = 0;
tail++;
while (1)
{
if (head == tail) break;
for (i = 0; i < 4; i++) // 상 하 좌 우
{
tmp_row = point[head].row + Dy[i];
tmp_col = point[head].col + Dx[i];
if (tmp_row >= 0 && tmp_row < N && tmp_col >= 0 && tmp_col < M) // MAP 범위 안에 존재
{
if (visited[tmp_row][tmp_col] == -1 && map[tmp_row][tmp_col] == 'L')
{
point[tail].row = tmp_row;
point[tail].col = tmp_col;
tail++;
visited[tmp_row][tmp_col] = visited[point[head].row][point[head].col] + 1; // 이전 위치보다 1칸 더 갔다는 뜻
// visited[tmp_row][tmp_col] = visited[tmp_row-Dy[i]][tmp_col-Dx[i]] + 1; 로 생각하는 게 더편함
if (visited[tmp_row][tmp_col] > max)
{
max = visited[tmp_row][tmp_col];
}
}
}
}
head++;
}
return max;
}
int main()
{
int i, j, k;
scanf("%d %d", &N, &M);
for (i = 0; i < N; i++)
{
scanf("%s", map[i]);
}
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
if (map[i][j] == 'L')
{
distance = bfs(i, j);
if (distance > max)
{
max = distance;
}
}
}
}
printf("%d\n", max);
}
//1번으로 구하는 것은 아래와 같음
//typedef struct {
// int sero;
// int garo;
//} _land;
//_land LAND[2500];
//_land POINT[250000];
//char map[50][50];
//int visited[50][50] = { 0, };
//
//int bfs(_land x, _land y)
//{
// memset(visited, -1, sizeof(visited));
// memset(POINT, -1, sizeof(POINT));
// int distance = 0;
// int head = 0;
// int tail = 0;
//
// int Dy[] = { -1,0,0,1 };
// int Dx[] = { 0 , -1, 1, 0 };
// int count = 0;
// while (head <= tail)
// {
// for (int i = 0; i < 4; i++)
// {
// int tmp_garo = Dx[i] + x.garo;
// int tmp_sero = Dy[i] + y.garo;
//
// if (tmp_sero == y.sero && tmp_garo == y.garo)
// {
// return count;
// }
// if (visited[tmp_sero][tmp_garo] == -1 && map[tmp_sero][tmp_garo] == 'L')
// {
// POINT[tail].garo = tmp_garo;
// POINT[tail].sero = tmp_sero;
// count++;
// tail++;
// }
// }
// head++;
// }
//
//}
//int main()
//{
// int sero;
// int garo;
//
//
// scanf("%d %d", &sero, &garo);
//
// for (int i = 0; i < sero; i++)
// {
// scanf("%s", map[i]);
// }
//
// // L의 위치 구하고, 배열에 넣기
// int idx = 0;
// for (int i = 0; i < sero; i++)
// {
// for (int j = 0; j < garo; j++)
// {
// if (map[i][j] == 'L')
// {
// LAND[idx].sero = i;
// LAND[idx].garo = j;
// idx++;
// }
// }
// }
// int max = 0;
// int tmp = 0;
// // 이미 가로 세로 위치 구한 애들이고 L들로 구성된 애들임.
// for (int i = 0; i < idx; i++)
// {
// for (int j = 1; j < idx - 1; j++)
// {
// tmp = bfs(LAND[i], LAND[j]);
// if (max < tmp)
// {
// max = tmp;
// }
// }
// }
// printf("%d", max);
//}