험난한 등굣길

[hye-on]

🔗 험난한 등굣길

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

#include <iostream>
#include <algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<tuple>

using namespace std;

//06:00


//모든 정체구역을 표시해주면 시간초과
//경계만 표시해주기. 중심부를 기준으로 다이아몬드 크기
//최악 1500 * 루트2 * 4 * 3000  

//최적화 : 거리순으로 내림차순으로 정렬해서 안그려도 되면 패스

int n, m, k;
vector<vector<int>>map;
bool exAns;
bool OOB(int y,int x) {
	if (y >= n || y < 0 || x >= m || x < 0)
		return true;
	return false;
}

int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };

void bfs() {
	
	queue<tuple<int,int,int>>q;
	q.push({ 0,0,0 });
	map[0][0] = 1;
	while (!q.empty()) {
		int curY = get<0>(q.front());
		int curX = get<1>(q.front());
		int d = get<2>(q.front());
		q.pop();

		if (curY == n - 1 && curX == m - 1) {
			cout << "YES" << "\n";
			cout << d;
			exAns = true;
			break;
		}

		for (int i = 0; i < 4; i++) {
			int ny = curY + dy[i];
			int nx = curX + dx[i];
			if (OOB(ny, nx) || map[ny][nx])
				continue;
			map[ny][nx] = 1;
			q.push({ ny,nx,d + 1 });
		}

	}

}



int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	cin >> n >> m;
	cin >> k;
	vector<vector<int>>tmp(n,vector<int>(m,0));
	map = tmp;
	int a = 0, b = 0, c = 0;
	int MoveR[4] = { -1,1,1,-1 };
	int MoveC[4] = { 1,1,-1,-1 };
	for (int i = 0; i < k; i++) {
		cin >> a >> b >> c;
		map[a-1][b-1] = 1;
		int NowR = a-1;
		int NowC = b - c-1;
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < c; k++) {
				NowR += MoveR[j];
				NowC += MoveC[j];
				if ((NowR >= 0) && (NowR <= n-1) && (NowC >= 0) && (NowC <= m-1)) {
					map[NowR][NowC] = 1;
				}
			}
		}
		
	}
	/*for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << map[i][j];
		cout << endl;
	}*/
	
	bfs();

	
	if (!exAns)
		cout << "NO";
}

코멘트

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

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

// 17:10 시작! 17:46 끗!
public class Main
{
    /**
     * 모든 k에 대해 정체 되는 칸을 구하고, bfs?
     */
    static boolean[][] map;
    static int[][] check; 
    static int n, m;
	public static void main(String[] args) throws Exception {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(bf.readLine());
	    n = Integer.parseInt(st.nextToken());
	    m = Integer.parseInt(st.nextToken());
	    map = new boolean[n+1][m+1];
	    check = new int[n+1][m+1];
	    for(int i = 0; i <= n; ++i) {
	        Arrays.fill(check[i], -1);
	    }
	    
	    int k = Integer.parseInt(bf.readLine());
	    int[][] regions = new int[k][3];
	    for(int i = 0; i < k; ++i) {
	        st = new StringTokenizer(bf.readLine());
	        int x = Integer.parseInt(st.nextToken());
	        int y = Integer.parseInt(st.nextToken());
	        int dist = Integer.parseInt(st.nextToken());
	        
	        regions[i] = new int[]{x, y, dist};
	    }
	    
	    Arrays.sort(regions, (a, b) -> b[2] - a[2]);
	    
	     for(int i = 0; i < k; ++i) {
	        mark(regions[i][0], regions[i][1], regions[i][2]);   
	     }
	    
	    Queue<int[]> q = new LinkedList<>();
	    q.offer(new int[]{1, 1});
	    boolean possible = false;
	    int level = 0;
	    while(!q.isEmpty()) {
	        int size = q.size();
	        for(int i = 0; i < size; ++i) {
	            int[] p = q.poll();
	            
	            for(int d = 0; d < 4; ++d) {
	                int nx = p[0] + dx[d];
	                int ny = p[1] + dy[d];
	                if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !map[nx][ny]) {
	                    if(nx == n && ny == m) {
	                        System.out.println("YES");
	                        System.out.println(level + 1);
	                        return;
	                    }
	                    
	                    q.offer(new int[]{nx, ny});
	                    map[nx][ny] = true;
	                }
	            }
	        }
	        
	        level++;
	    }
	    
	    System.out.println("NO");
	}
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	public static void mark(int x, int y, int dist) {
	    if(check[x][y] > dist) return; // 이미 마킹 했으면
	    
	    Queue<int[]> q = new LinkedList<>();
	    q.offer(new int[]{x, y});
	    map[x][y] = true;
	    check[x][y] = dist;
	    
	    int level = 0;
	    while(!q.isEmpty()) {
	        if(level == dist) break;
	        
	        int size = q.size();
	        for(int i = 0; i < size; ++i) {
	            int[] p = q.poll();
	            
	            for(int d = 0; d < 4; ++d) {
	                int nx = p[0] + dx[d];
	                int ny = p[1] + dy[d];
	                if(nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
	                    if(check[nx][ny] >= dist - (level + 1)) continue;
	                    check[nx][ny] = dist - (level + 1);
	                    map[nx][ny] = true;
	                    q.offer(new int[]{nx, ny});
	                }
	            }
	        }
	        
	        ++level;
	    }
	}
}

코멘트

- BFS + DP로 풀었습니다! 정체 구간을 구할 때, 모든 K에 대해 마킹을 하면 시간 초과가 발생해서.. DP로 이미 마킹한 곳은 다시 마킹하지 않도록 했습니다..!