[2021 카카오 채용연계형 인턴십][BFS] 거리두기 확인하기 - Java

문제 바로가기

코딩테스트 연습 - 거리두기 확인하기

 

또 오랜만입니다.. ㅎ

그동안 이펙티브 자바는 꾸준히 정리했지만 문제 푸는건 쉽지 않네요.

그래서 친구들이랑 같이 공부하기로 했습니다!! 호호

 

이번 문제는 아주아주 간단한 BFS 문제 입니다.

근데 30분이나 걸렸습니다 ;; 예전 같았으면~~~ 10분도 안걸렸을텐데~~~~ㅜ

 

import java.util.*;

class Solution {
  final int LEN = 5;
  final int[] dy = {1, -1, 0, 0};
  final int[] dx = {0, 0, 1, -1};

  static class Dir {
    int y, x;
    Dir(int y, int x) {
      this.y = y; this.x = x;
    }
  }

  public int[] solution(String[][] places) {
    int[] answer = new int[LEN];

    for(int i = 0; i < LEN; i++) {
      answer[i] = makeResult(convertArray(places[i]));
    }

    return answer;
  }

  public int makeResult(char[][] place) {
    List<Dir> people = new ArrayList<>();

    // 리스트에 사람 위치 다 넣기
    for(int i = 0; i < LEN; i++) {
      for(int j = 0; j < LEN; j++) {
        if(place[i][j] == 'P') {
          people.add(new Dir(i, j));
        }
      }
    }

    // 한 사람 당 거리 체크 필요
    for(Dir person : people) {
      if(!isValidDistance(place, person)) return 0;
    }

    return 1;
  }

  public boolean isValidDistance(char[][] place, Dir start) {
    Queue<Dir> q = new LinkedList<>();
    int[][] dist = new int[LEN][LEN];

    q.offer(start);
    dist[start.y][start.x] = 1;

    while(!q.isEmpty()) {
      Dir cur = q.poll();

      for(int i = 0; i < 4; i++) {
        Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
        // 맵 벗어나거나 || 이미 방문한 곳이거나 || 파티션의 경우
        if (!isIn(next) || dist[next.y][next.x] != 0 || place[next.y][next.x] == 'X') continue;

        dist[next.y][next.x] = dist[cur.y][cur.x] + 1;
        if (place[next.y][next.x] == 'P' && dist[next.y][next.x] <= 3) return false;

        q.offer(next);
      }
    }

    return true;
  }

  public boolean isIn(Dir c) {
    if(0 <= c.y && c.y < LEN && 0 <= c.x && c.x < LEN) return true;
    else return false;
  }

  public char[][] convertArray(String[] place) {
    char[][] map = new char[LEN][LEN];
    for(int i = 0; i < LEN; i++) {
      for(int j = 0; j < LEN; j++) {
        map[i][j] = place[i].charAt(j);
      }
    }

    return map;
  }
}

 

이렇게 길 코드가 아닌데.. 어쩌다보니 쫌 장황하게 풀었습니다.

먼저 대기실의 행/열이 5이고, 대기실의 개수도 5개로 정해져있어서 상수를 하나 선언해서 보기가 이쁩니다.

 

어렵게 생각할 거 하나도 없고 사람이 있는 위치에서 BFS 를 돌리면 됩니다.

특별히 신경쓸 것도 없습니다.

파티션빼고 BFS를 돌다가 사람을 만났다?? 근데 얘랑 거리가 3이 안된다?? 그럼 아묻따 0을 리턴해버리면 됩니다.

 

저는 개인적으로 문자열 배열로 표현된 2차원 배열을 상당히 혐오하기 때문에 2차원짜리 char 배열로 변환해서 써먹었습니다.

 

 

오랜만에 푸니깐 재밌네요. 근데 세상엔 훨씬 더 재밌는 일이 많으니깐 언제 돌아올진 장담 못합니다.

그럼 20000