[백준] BOJ_6087 레이저통신

문제

BOJ 6087 레이저통신

https://www.acmicpc.net/problem/6087

인생 쓰다...
시간 초과의 늪에 빠져버린 김앙주
과연 앙주는 이 난관을 어떻게 헤쳐나갈까? 두둥탁🥁🥁

코드

시간초과 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int W, H;
	static char[][] map;
	static boolean[][] visit;
	static int [][]mapCnt;
	static node[] nd;
	static int min=10_000;
	
	static int[][] dir= {{0,1},{0,-1},{1,0},{-1,0}};

	static class node {
		int y, x;

		node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		map = new char[H][W];
		visit=new boolean[H][W];
		mapCnt=new int[H][W];
		
		nd = new node[2];
		int ndCnt = 0;

		
		// 지도 꾸리기 & 목표좌표, 시작좌표 구하기
		for (int i = 0; i < H; i++) {
			map[i] = br.readLine().toCharArray();
			Arrays.fill(mapCnt[i],10_000);
			
			//c 다 구하면 굳이 for문 돌지 않기
			if (ndCnt <= 1) {
				for (int j = 0; j < W; j++) {
					if (map[i][j] == 'C') {
						nd[ndCnt] = new node(i, j);
						ndCnt++;
					}
					if (ndCnt > 1)
						break;
				}
			}

		}
		cal(nd[0].y,nd[0].x,0,0,0);
		System.out.println(min);

	}
	
	static void cal(int y,int x,int cnt,int d,int dCnt) {
		
		//멈출 때 (기저조건)
		if(y==nd[1].y&&x==nd[1].x) {
			min=Math.min(min,dCnt);
			return;
		}
		
		if(dCnt>min)return;
		
		mapCnt[y][x]=dCnt;
		
		for(int i=0;i<4;i++) {
			int ny=y+dir[i][0];
			int nx=x+dir[i][1];
			
			//조건 안 맞을 때
			if(ny>=H||ny<0||nx>=W||nx<0||map[ny][nx]=='*'||visit[ny][nx]) {
				continue;
			}
			
			//방문 표시
			visit[ny][nx]=true;
			
		
			// 방향 전환 
			if(cnt>0&&i!=d) {
				if(mapCnt[ny][nx]>=dCnt+1) {
					cal(ny,nx,cnt+1,i,dCnt+1);
				}
			}else {
				if(mapCnt[ny][nx]>=dCnt) {
				cal(ny,nx,cnt+1,i,dCnt);
				}
			}
			
			visit[ny][nx]=false;
		}
	}

}

백트래킹으로 문제를 풀었다.
가지치기를 잘 하면 시간 내에 들어올 줄 알았다.
난 여전히 시간복잡도를 잘 계산하지 못하나 보다....
재기로 문제를 푼 사람들이 있을까?
코드 좀 보여줬음 좋겠다.

bfs로 해~결!🤡

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
 
public class Main {
 
    static int W, H;
    static char map[][];
    static int[][] dist;
    static node start, end;	
    static int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 };
 
    static class node {
        int x, y;
 
        public node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new char[H][W];
      
        boolean isStart = false;
        
        for (int i = 0; i < H; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < W; j++) {
                
                if (map[i][j] == 'C') {
             
                    if (!isStart) {
                        start = new node(i, j);
                        isStart = true;
                    } else
                        end = new node(i, j);
                }
            }
        }
 
        cal();
        System.out.println(dist[end.x][end.y] - 1);
    }
 
    private static void cal() {
 
        Queue<node> q = new ArrayDeque<>();
        dist = new int[H][W];
        
        q.add(start);
 
        while (!q.isEmpty()) {
            node nd = q.poll();
            if(dist[end.x][end.y] != 0) return;
            // 4방 탐색
            for (int d = 0; d < 4; d++) {
                int nx = nd.x + dx[d];
                int ny = nd.y + dy[d];
               
                while (nx >= 0 && ny >= 0 && nx < H && ny < W && map[nx][ny] != '*') {
                    if (dist[nx][ny] == 0) {
                        dist[nx][ny] = dist[nd.x][nd.y] + 1;
                        q.add(new node(nx, ny));
                    }
                    nx += dx[d];
                    ny += dy[d];
                }
            }
        }
        
        return;
    }
}

재기로는 도저히 풀지 못할 것 같아 급히 노선을 바꿔보았다!
그리곤 풀렸다 룰루~~~

오알완 안농