Portfolio

문제

풀이

재영

~~3시간 걸렸......~~


/**
 * NOTE:
 * L: 0
 * R: 1
 * U: 2
 * D: 3
 */
const directions = {
  0: [0, -1],
  1: [0, 1],
  2: [-1, 0],
  3: [1, 0],
};

// nextDirections[기준 위치의 기호][이전 방향] = 다음 방향
const nextDirections = {
  L: {
    0: 3,
    1: 2,
    2: 0,
    3: 1,
  },
  R: {
    0: 2,
    1: 3,
    2: 1,
    3: 0,
  },
  S: {
    0: 0,
    1: 1,
    2: 2,
    3: 3,
  },
};

// 3차원 배열로 변환시킴
const make3DemensionArray = (grid) => {
  const arr = JSON.parse(JSON.stringify(grid));

  for (let i = 0; i < arr.length; i += 1) {
    arr[i] = arr[i].split('');

    for (let j = 0; j < arr[i].length; j += 1) {
      arr[i][j] = [arr[i][j], [false, false, false, false]];
    }
  }

  return arr;
};

// 다음 x, y 좌표를 만들어줌.
const getNextXY = (x, y, direction, xLength, yLength) => {
  const [dx, dy] = directions[direction];

  let nx = x + dx;
  let ny = y + dy;

  if (nx === xLength) {
    nx = 0;
  } else if (nx < 0) {
    nx = xLength - 1;
  }

  if (ny === yLength) {
    ny = 0;
  } else if (ny < 0) {
    ny = yLength - 1;
  }

  return [nx, ny];
};

const bfs = (arr, startX, startY, startDirection, initData) => {
  const result = [];

  const queue = [];
  const xLength = arr.length;
  const yLength = arr[0].length;

  arr[startX][startY][1][startDirection] = true;
  queue.push(initData);

  while (queue.length) {
    const [nowX, nowY, nowD, count] = queue.shift();
    arr[nowX][nowY][1][nowD] = true;

    const [nextX, nextY] = getNextXY(nowX, nowY, nowD, xLength, yLength);
    const nextValue = arr[nextX][nextY][0];
    const nextDirection = nextDirections[nextValue][nowD];
    const nextCount = count + 1;

    if (arr[nextX][nextY][1][nextDirection]) {
      if (
        nextX === startX &&
        nextY === startY &&
        startDirection === nextDirection
      ) {
        result.push(nextCount);
      }
      continue;
    }

    queue.push([nextX, nextY, nextDirection, nextCount]);
  }

  return result;
};

const solution = (grid) => {
  const result = [];

  const arr = make3DemensionArray(grid);
  const xLength = arr.length;
  const yLength = arr[0].length;

  for (let i = 0; i < xLength; i += 1) {
    for (let j = 0; j < yLength; j += 1) {
      for (let k = 0; k < 4; k += 1) {
        if (!arr[i][j][1][k]) {
          result.push(...bfs(arr, i, j, k, [i, j, k, 0])); // nowX, nowY, nowD, count
        }
      }
    }
  }

  return [...result].sort((a, b) => a - b);
};

은찬


function solution(grid) {
    const answer = [];
    const m = grid.length;
    const n = grid[0].length;
    const direct = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const visited = Array.from({length: m}, () => Array.from({length: n}, () => Array(4).fill(false)));
        
    const go = (x, y, from) => {
        let nx = x;
        let ny = y;
        let to = from;
        
        switch(grid[x][y]){
            case "S":
                if(from === 0){
                    nx--;
                } else if(from === 1){
                    nx++;
                } else if(from === 2){
                    ny--;
                } else if(from === 3){
                    ny++;
                }
                break;
            case "L":
                if(from === 0){
                    ny--;
                    to = 2;
                } else if(from === 1){
                    ny++;
                    to = 3;
                } else if(from === 2){
                    nx++;
                    to = 1;
                } else if(from === 3){
                    nx--;
                    to = 0;
                }
                break;
            case "R":
                if(from === 0){
                    ny++;
                    to = 3;
                } else if(from === 1){
                    ny--;
                    to = 2;
                } else if(from === 2){
                    nx--;
                    to = 0;
                } else if(from === 3){
                    nx++;
                    to = 1;
                }
                break;
        }
        
        nx = nx < 0 ? m - 1 : nx === m ? 0 : nx;
        ny = ny < 0 ? n - 1 : ny === n ? 0 : ny;
        
        return [nx, ny, to];
    }
    
    const bfs = (x, y, d) => {
        const queue = [[x, y, d, 0]];
        
        while(queue.length){
            const [cx, cy, cd, len] = queue.shift();
            const [nx, ny, nd] = go(cx, cy, cd);
            
            if(visited[cx][cy][cd]){
                answer.push(len);
                
                return;
            }
            
            visited[cx][cy][cd] = true;
            queue.push([nx, ny, nd, len + 1]);
        }
    }
    
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            for(let k = 0; k < 4; k++){
                if(!visited[i][j][k]){
                    bfs(i, j, k);
                }
            }
        }
    }
    
    return answer.sort((a, b) => a - b);
}

빛의 경로 사이클

문제

풀이