문제 설명
보통 보물의 위치가 정해져 있고 특정 위치에서 해당 보물들을 찾는 문제라면, 이 문제는 그 보물을 직접 찾고 최단거리를 출력해야 합니다. 이 문제를 읽고 나면 아래와 같은 의문점이 생깁니다.
- 보물을 찾는 방법?
- 최단 거리는 어떻게 구할 것인가?
- 같은 좌표인데 거리가 다른경우?
- 좌표가 같다면 거리가 짧은 것으로 갱신
- 아예 bfs를 써서 돌리면 최단 거리에서 return되기 때문에 걱정없음
이처럼 여러 가지 의문점이 생겼었는데 정리하자면 이렇습니다.
BFS로 탐색을 수행하면 가장 먼저 return 되는 값이 최단거리입니다.
그렇기에 위 그림처럼 길이가 더 긴 거리가 MAX값이 될 일은 없습니다.
필드의 width, height 크기만큼 반복문을 수행했고 모든 좌표를 탐색합니다.
(물론 값 입력 시에 L 필드의 좌표만 따로 저장해두셨다가 돌리셔도 좋습니다.)
L필드를 찾았다면 bfs를 수행합니다.
여기서, bfs에서는 최단거리를 반환합니다.
반환된 값이 다른 경로 최단거리보다 크다면 max를 갱신해주고 최종적으로 모든 반복문이 종료되면(모든 L 탐색이 끝나면) max를 출력해 줍니다.
Java와 Python의 로직은 동일합니다.
소스 코드
Python
from collections import deque
H,W = map(int,input().split())
field = list()
direction = [[0,1],[1,0],[-1,0],[0,-1]]
for _ in range(H):
field.append(list(input()))
def bfs(rx,ry):
visited = [[0]*W for _ in range(H)]
q = deque([[rx,ry]])
visited[ry][rx]=1
maxcnt = 0
while q:
x,y = q.popleft()
for dx,dy in direction:
nx,ny = dx+x,dy+y
if 0<=nx<W and 0<=ny<H and field[ny][nx]=='L' and visited[ny][nx]==0:
visited[ny][nx]=visited[y][x]+1
if maxcnt < visited[ny][nx]:maxcnt=visited[ny][nx]
q.append([nx,ny])
return maxcnt-1
answer = 0
for i in range(H):
for j in range(W):
if field[i][j]=='L':
tmp = bfs(j,i)
if tmp>answer:
answer = tmp
print(answer)
Java8
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static class node{
int x,y;
node(int x,int y){
this.x = x;
this.y = y;
}
}
static int H,W;
static char field[][];
static int dirx[]= {0,1,-1,0};
static int diry[]= {1,0,0,-1};
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int bfs(int rx, int ry) {
int visited[][] = new int[H][W];
visited[ry][rx]=1;
Deque<node> q = new LinkedList<node>();
node n = new node(rx,ry);
q.addLast(n);
int maxcnt = 0 ;
while(!q.isEmpty()) {
node qxy = q.pollFirst();
for(int i = 0 ; i <4;i++) {
int nextX = qxy.x + dirx[i];
int nextY = qxy.y + diry[i];
if(0<=nextX && nextX<W && 0<=nextY && nextY<H && field[nextY][nextX]=='L' && visited[nextY][nextX]==0) {
visited[nextY][nextX]=visited[qxy.y][qxy.x]+1;
if(maxcnt<visited[nextY][nextX])maxcnt=visited[nextY][nextX];
node nnd = new node(nextX,nextY);
q.addLast(nnd);
}
}
}
return maxcnt-1;
}
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
field = new char[H][W];
for(int i = 0 ; i < H;i++) {
st = new StringTokenizer(br.readLine());
String tmp = st.nextToken();
for(int j = 0 ; j < W;j++)
field[i][j] = tmp.charAt(j);
}
int max = 0;
for(int i = 0 ; i < H;i++)
for(int j = 0 ; j < W; j++) {
if(field[i][j]=='L') {
int tmp = bfs(j,i);
if (max<tmp)max=tmp;
}
}
System.out.println(max);
}
}
