[SW Expert Academy] 4193. 수영대회 결승전 ( 완전 탐색 + 구현 )

문제

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV&categoryId=AWKaG6_6AGQDFARV&categoryType=CODE

풀이

import java.util.*;
import java.lang.*;
import java.io.*;

class Pos implements Comparable<Pos>{
    int time;
    int nextX;
    int nextY;

    public Pos(int time,int nextX,int nextY){
        this.time=time;
        this.nextX=nextX;
        this.nextY=nextY;
    }

    @Override
    public int compareTo(Pos other){
        if(this.time!=other.time){
            return Integer.compare(this.time,other.time);
        }else if(this.nextX!=other.nextX){
            return Integer.compare(this.nextX,other.nextX);
        }
        return Integer.compare(this.nextY,other.nextY);
    }
    @Override
    public String toString(){
        return "("+time+", "+nextX+", "+nextY+")";
    }
}

class Solution {
    public static void main(String[] args) {
        int[] dx={-1,1,0,0};
        int[] dy={0,0,-1,1};
        
        Scanner s=new Scanner(System.in);
        int tc=s.nextInt();
        for(int i=1;i<=tc;i++){
            int n=s.nextInt();
            int[][] board=new int[n][n];
            int[][] visited=new int[n][n];
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    board[j][k]=s.nextInt();
                }
            }
            int sx=s.nextInt();
            int sy=s.nextInt();
            int tx=s.nextInt();
            int ty=s.nextInt();
            PriorityQueue<Pos> q=new PriorityQueue<>();
            q.add(new Pos(0,sx,sy));
            while(!q.isEmpty()){
                Pos p=q.poll();
                if(p.nextX==tx && p.nextY==ty){
                    System.out.printf("#%d %d\n",i,p.time);
                    break;
                }
                for(int j=0;j<4;j++){
                    int nx=p.nextX+dx[j];
                    int ny=p.nextY+dy[j];
                    int nt=0;
                    if(nx<0 || ny<0 || nx>=n || ny>=n){
                        continue;
                    }
                    if(board[nx][ny]==1){
                        continue;
                    }
                    if(visited[nx][ny]==1){
                        continue;
                    }
                    visited[nx][ny]=1;
                    if(board[nx][ny]==2){
                        nt=p.time+3-p.time%3;
                    }else{
                        nt=p.time+1;
                    }
                    q.add(new Pos(nt,nx,ny));
                }
            }
            if(visited[tx][ty]==0){
                System.out.printf("#%d %d\n",i,-1);
            }
        }
    }
}

내 생각

• 의외로 빨리 결론에 접근하고 다 풀어놓고 마지막 '-1' 출력하는 걸로 한 10~15분 헤맨듯 하다...
• 전형적인 BFS문제로 최단거리를 구하는 문제이다. 전체 최대 크기가 한 변에 15이기 때문에 O(N)인 BFS로 충분히 풀만하다. 각 시간을 기록해나가면서 풀면되는데 이 때, 기존의 BFS 알고리즘처럼 Queue를 쓰면 시간보다는 거리 우선적으로 기록이 되기 때문에, 거리가 먼저 해당 지점에 방문에 버려 시간 우선이 되지 않을 수 있다. 그렇기 때문에, 시간 우선적으로 기록되게 하기 위해 PriorityQueue, 즉 우선순위큐를 사용하여 진행해주면된다. 우선순위큐를 사용하여도 O(nlogn)이기 때문에 충분히 가능하다.
• 시작지점을 기준으로 각 가능한 방향을 고려하고 해당 방향에 대하여 방문조건, 장애물 조건, 장외 조건 등을 고려하며 나아가면 된다. 이 때, 시간을 우선순위큐에 담아 진행하며 시간의 경우는 기존의 시간에서 소용돌이가 아니면 +1을 소용돌이라면 시간에 따라 진행시간 기준으로 3초에서 기존시간을 3으로 나눈 나머지를 뺀 값이 '대기시간'이 되기 때문에 이 값을 더해주면된다.
• 마지막으로 도달하지 못한경우 while문을 나온다음 visited가 방문되지 못했다면 -1을 출력해주면 된다.
• 풀이시간 : 35분

추가적인 Python 풀이

import heapq

dx=[0,0,-1,1]
dy=[-1,1,0,0]

for tc in range(int(input())):
    n=int(input())
    board=[]
    for i in range(n):
        board.append(list(map(int,input().split())))
    start_x,start_y=map(int,input().split())
    target_x,target_y=map(int,input().split())
    q=[]
    heapq.heappush(q,(0,start_x,start_y))
    visited=[[False]*n for _ in range(n)]
    visited[start_x][start_y]=True
    while q:
        t,x,y=heapq.heappop(q)
        if x==target_x and y==target_y:
            print("#"+str(tc+1)+" "+str(t))
            break
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            nt=0
            if nx<0 or ny<0 or nx>=n or ny>=n:
                continue
            if board[nx][ny]==1:
                continue
            if visited[nx][ny]:
                continue
            visited[nx][ny]=True
            if board[nx][ny]==2:
                nt=t+3-t%3
            else:
                nt=t+1
            heapq.heappush(q,(nt,nx,ny))
            

• 파이썬이 주 코테 언어다보니 빠르게 파이썬으로 작성하였다. 20분 정도만에 해결한거 같다.