처음엔 파이썬으로 짰는데 시간초과가 떴다. 답은 맞다고 생각해서 C++로 바꿨더니 성공했다.
# -*- encoding: cp949 -*-
import Queue, copy
def bfs(y,x,k):
global temp_map
visited = [[0 for j in xrange(n)] for i in xrange(n)]
q = Queue.Queue()
q.put([y,x])
temp_map[y][x] = safe_area
visited[y][x] = 1
while not q.empty():
p = q.get()
for i in xrange(4):
y,x = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
if y>n-1 or x>n-1 or x<0 or y<0:
continue
if visited[y][x]==0 and temp_map[y][x] > k and temp_map[y][x] > 0:
q.put([y,x])
visited[y][x] = 1
temp_map[y][x] = safe_area
#print '\n'.join(map(str,temp_map))
#print
n = int(raw_input())
maps = [map(int,raw_input().split()) for i in xrange(n)]
h = max(map(max,maps))
#print 'l,h =',l,h,'\n'
answer = []
for k in xrange(h):
safe_area = 0
temp_map = copy.deepcopy(maps)
for i in xrange(n):
for j in xrange(n):
if temp_map[i][j] > k and temp_map[i][j] > 0:
safe_area -= 1
bfs(i,j,k)
#print k,-safe_area
answer.append(-safe_area)
print max(answer)
#include <iostream>
#include <queue>
using namespace std;
int maps[101][101];
int temp_map[101][101];
int n;
int yi[] = {1,0,-1,0};
int xi[] = {0,-1,0,1};
void bfs(int y,int x, int k, int safe_area)
{
int visited[101][101];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
visited[i][j] = 0;
queue<int> qy; queue<int> qx;
qy.push(y); qx.push(x);
temp_map[y][x] = safe_area;
visited[y][x] = 1;
while(!qy.empty())
{
int py = qy.front();
int px = qx.front();
qy.pop(); qx.pop();
for(int i=0;i<4;i++)
{
int y = py+yi[i];
int x = px+xi[i];
if(y>n-1 || x>n-1 || x<0 || y<0)
continue;
if(visited[y][x]==0 && temp_map[y][x] > k && temp_map[y][x] > 0)
{
qy.push(y); qx.push(x);
visited[y][x] = 1;
temp_map[y][x] = safe_area;
}
}
}
}
int main()
{
cin>>n;
int max = 0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>maps[i][j];
if(maps[i][j] > max)
max = maps[i][j];
}
int answer = 0;
for(int k=0;k<max;k++)
{
int safe_area = 0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
temp_map[i][j] = maps[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(temp_map[i][j] > k && temp_map[i][j] > 0)
{
safe_area--;
bfs(i,j,k,safe_area);
}
//cout<<k<<" "<<-safe_area<<endl;
if(-safe_area > answer)
answer = -safe_area;
}
cout<<answer<<endl;
return 0;
}
# -*- encoding: cp949 -*-
import Queue
import copy
move_list = []
def bfs(y,x):
temp_map = copy.deepcopy(maps)
move = 0
visited = [[0 for j in xrange(W)] for i in xrange(H)]
q = Queue.Queue()
q.put([y,x])
visited[y][x] = 1
while not q.empty():
for k in xrange(q.qsize()):
p = q.get()
for i in xrange(4):
y,x = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
if y>H-1 or x>W-1 or x<0 or y<0:
continue
if visited[y][x]==0 and temp_map[y][x]=='L':
q.put([y,x])
visited[y][x] = 1
move += 1
move_list.append(move-1)
H,W = map(int,raw_input().split())
maps = [list(raw_input()) for i in xrange(H)]
for i in xrange(H):
for j in xrange(W):
if maps[i][j]=='L':
bfs(i,j)
print max(move_list)
#include <iostream>
#include <queue>
using namespace std;
char maps[51][51];
int treasure = -1;
int H,W;
int yi[] = {1,0,-1,0};
int xi[] = {0,-1,0,1};
void bfs(int y,int x)
{
char temp_map[51][51];
for(int i=0;i<H;i++) //temp_map에 복사해둠.
for(int j=0;j<W;j++)
temp_map[i][j] = maps[i][j];
int move = 0; //이동한 거리
int visited[51][51] = {0,};
queue<int> qy; queue<int> qx;
qy.push(y); qx.push(x);
visited[y][x] = 1;
while(!qy.empty())
{
int size = qy.size();
for(int i=0;i<size;i++)
{
int py = qy.front();
int px = qx.front();
qy.pop(); qx.pop();
for(int j=0;j<4;j++) //4방향을 다 돌면서 찾기
{
int ty = py + yi[j];
int tx = px + xi[j];
if(ty>H-1 || tx>W-1 || tx<0 || ty<0) //벗어나면 무시
continue;
if(visited[ty][tx]==0 && temp_map[ty][tx]=='L')
{
qy.push(ty); qx.push(tx);
visited[ty][tx] = 1;
}
}
//cout<<t1<<" "<<t2<<endl;
}
move++;
//cout<<"m = "<<move<<endl;
if(move-1 > treasure) //가장 많은 걸음수 갱신
treasure = move-1;
}
}
int main()
{
cin>>H>>W;
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
cin>>maps[i][j];
for(int i=0;i<H;i++) //다 돌면서 검색
for(int j=0;j<W;j++)
if(maps[i][j]=='L')
bfs(i,j);
cout<<treasure<<endl;
return 0;
}