[PCCP] Lv2: 방문 길이(49994) 해설

문제

- 문제 링크: 방문 길이

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

- 중복 경로 처리

- 음수 좌표 처리

- 기능별 함수 구현

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: dirs의 길이

- dirs의 길이만큼 순회: O(N)

#include <string>

using namespace std;

// 특정 좌표에서 특정 방향으로 이동한 적이 있는지 체크
bool visited[11][11][4];

// 상하좌우로 좌표를 이동할 때 필요한 좌표 오프셋 배열
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

// 각 문자에 해당하는 오프셋 배열의 인덱스를 반환
int todir(char dir) {
    int ret;
    if (dir == 'U')
        ret = 0;
    else if (dir == 'R')
        ret = 1;
    else if (dir == 'D')
        ret = 2;
    else
        ret = 3;
    return ret;
}

// 특정 좌표가 주어진 좌표 평면을 벗어나는지 확인
bool isNotValid(int x, int y) {
    return x < 0 || y < 0 || x > 10 || y > 10;
}

// 현재와 반대 방향의 오프셋 배열 인덱스 반환
int opposite_direction(int dir) {
    return (dir + 2) % 4;
}

int solution(string dirs) {
    int answer = 0;
    int x = 5, y = 5; // 시작 좌표

    for (auto c : dirs) {
        // 반복문을 순회하며 nx, ny는 x, y가 dirs대로 움직였을 때 위치가 됨
        int dir = todir(c);
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        // 좌표 평면을 벗어나면 더 이상 이동하지 않음
        if (isNotValid(nx, ny)) {
            continue;
        }
        
        // 다음 좌표가 아직 방문하지 않은 좌표인 경우
        if (visited[y][x][dir] == false) {
            // 방문을 중복 체크하지 않도록 해당 경로의 양방향 방문을 체크
            visited[y][x][dir] = true;
            visited[ny][nx][opposited_direction(dir)] = true;
            answer++;
        }
        
        // 현재 좌표를 이동한 좌표로 업데이트
        x = nx;
        y = ny;
        
    }

    return answer;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: dirs의 길이

- dirs의 길이만큼 순회하므로 최종 시간 복잡도: O(N)

import java.util.HashMap;
import java.util.HashSet;

class Solution {
    // 좌표평면을 벗어나는지 체크하는 메서드
    private static boolean isValidMove(int nx, int ny) {
        return 0 <= nx && nx < 11 && 0 <= ny && ny < 11;
    }
    
    // 다음 좌표 결정을 위한 해시맵 생성
    private static final HashMap<Character, int[]> location = new HashMap<>();
    
    private static void initLocation() {
        location.put('U', new int[]{0, 1});
        location.put('D', new int[]{0, -1});
        location.put('L', new int[]{-1, 0});
        location.put('R', new int[]{1, 0});
    }
    
    public int solution(String dirs) {
        initLocation();
        int x = 5, y = 5;
        HashSet<String> answer = new HashSet<>(); // 겹치는 좌표는 1개로 처리하기 위함
        // 주어진 명령어로 움직이면서 좌표 저장
        for (int i = 0; i < dirs.length(); ++i) {
            int[] offset = location.get(dirs.charAt(i));
            int nx = x + offset[0];
            int ny = y + offset[1];
            if (!isValidMove(nx, ny)) // 벗어난 좌표는 인정하지 않음
                continue;
            // A에서 B로 간 경우 B에서도 A도 추가해야 함(총 경로의 개수는 방향성이 없음)
            answer.add(x + " " + y + " " + nx + " " + ny);
            answer.add(nx + " " + ny + " " + x + " " + y);
            // 좌표를 이동했으므로 업데이트
            x = nx;
            y = ny;
        }
        return answer.size() / 2;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: dirs의 길이

- dirs의 길이만큼 순회: O(N)

def is_valid_move(nx, ny): # 좌표평면을 벗어나는지 체크하는 함수
    return 0 <= nx < 11 and 0 <= ny < 11
    
def update_location(x, y, dir): # 명령어를 통해 다음 좌표 결정
    if dir == "U":
        nx, ny = x, y + 1
    elif dir == "D":
        nx, ny = x, y - 1
    elif dir == "L":
        nx, ny = x - 1, y
    elif dir == "R":
        nx, ny = x + 1, y
    return nx, ny

def solution(dirs):
    x, y = 5, 5
    ans = set() # 겹치는 좌표는 1개로 처리하가 위함
    for dir in dirs: # 주어진 명령어로 움직이면서 좌표 저장
        nx, ny = update_location(x, y, dir)
        if not is_valid_move(nx, ny): # 벗어난 좌표는 인정하지 않음
            continue
        # A에서 B로 간 경우 B에서 A로 추가해야 함(총 경로의 개수는 방향성이 없음)
        ans.add((x, y, nx, ny))
        ans.add((nx, ny, x, y))
        x, y = nx, ny # 좌표를 이동했으므로 업데이트
    return len(ans)/2

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: dirs의 길이

- dirs의 길이만큼 순회: O(N)

function isValidMove(nx, ny) {
    // 좌표평면을 벗어나는지 체크하는 함수
    return nx >= -5 && nx <= 5 && ny >= -5 && ny <= 5;
}

function updateLocation(x, y, dir) {
    // 명령어를 통해 다음 좌표 결정
    switch(dir) {
        case "U":
            return [x, y + 1];
        case "D":
            return [x, y - 1];
        case "R":
            return [x + 1, y];
        case "L":
            return [x - 1, y];
    }
}

function solution(dirs) {
    let x = 0;
    let y = 0;
    
    const visited = new Set(); // 겹치는 좌표는 1개로 처리하기 위함
    for (const dir of dirs) {
        // 주어진 명령어로 움직이면서 좌표 저장
        const [nx, ny] = updateLocation(x, y, dir);
        
        if (!isValidMove(nx, ny)) {
            // 벗어난 좌표는 인정하지 않음
            continue;
        }
        
        // A에서 B로 간 경우 B에서 A도 추가해야 함(총 경로의 개수는 방향성이 없음)
        visited.add(`${x}${y}${nx}${ny}`);
        visited.add(`${nx}${ny}${x}${y}`);
        
        [x, y] = [nx, ny]; // 좌표를 이동했으므로 업데이트
    }
    
    return visited.size / 2;
}

solution 2)

import

solution 3)

import