강승현입니다
article thumbnail
반응형

문제로이동

 

2589번: 보물섬

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서

www.acmicpc.net


목차

     



    문제 설명

    보통 보물의 위치가 정해져 있고 특정 위치에서 해당 보물들을 찾는 문제라면, 이 문제는 그 보물을 직접 찾고 최단거리를 출력해야 합니다. 이 문제를 읽고 나면 아래와 같은 의문점이 생깁니다.

    • 보물을 찾는 방법?
    • 최단 거리는 어떻게 구할 것인가?
    • 같은 좌표인데 거리가 다른경우?
      • 좌표가 같다면 거리가 짧은 것으로 갱신
      • 아예 bfs를 써서 돌리면 최단 거리에서 return되기 때문에 걱정없음

    이처럼 여러 가지 의문점이 생겼었는데 정리하자면 이렇습니다.

     

    출발점과 도착점은 같지만 이동 거리가 8, 10으로 다르다.

    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);
    	}
    }
    
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    article prev thumbnail
    article next thumbnail
    profile on loading

    Loading...