LEVEL 3 : 리틀 프렌즈 사천성

https://programmers.co.kr/learn/courses/30/lessons/1836

코딩테스트 연습 - 리틀 프렌즈 사천성

 

• 문제

  • 

    문제 1

  • 

    문제 2

  • 

    문제 3

---

풀이

• BFS로 풀이하면 되는 문제이다(쉽지 않지만 구현하기가 까다로웠다ㅠ_ㅠ)
• initArrayList = Character 형 List를 선언하고 모든 쓰촨 성이 연결될 수 있는 요소를 다 넣어준다.
  
  • '.' , '*' 의 제외한 모든 요소들
  • List에 넣은 뒤 넣은 요소를 기준으로 정렬한다.
    • 정렬 기준 1 : 알파벳 순으로 요소를 정렬
    • 정렬 기준 2 : 알파벳이 같은 요소일 경우 x, y 좌표가 낮은 순으로 정렬한다.
  • 타일은 반드시 두개의 쌍으로 존재하기 때문에, 같은 타일끼리 뭉쳐지게 된다
• i값이 2씩 증가하는 list를 도는 for문을 만든다.
  • list(i) 요소와 list(i+1) 번째는 무조건 쌍이기 때문에
  • 모든 요소를 list에서 다 지울수 있다면 정답을 반환하고, 아니면 불가능한 경우이니 IMPOSSIBLE을 반환한다.
  • list를 지우기 위해서는 canRemove 함수에서 true 를 반환해야 한다.
• canRemove 함수
  • 경우 1 : 두개의 쌍의 y좌표가 같다 -> 같은 행에 존재하는 데이터
    • 첫 번째 Puzzle의 x+1 좌표부터 두 번째  Puzzle의 x-1 좌표까지 모두 '.' 이어야 된다(벽이나, 다른 것들이 막고 있으면 안 된다.
  • 경우 2 : 두 개의 쌍의 x좌표가 같다 -> 같은 열에 존재하는 데이터
    • 첫 번째 Puzzle의 y+1 좌표부터 두 번째 Puzzle의 y-1 좌표까지 모두 '.' 이어야 된다(벽이나, 다른 것들이 막고 있으면 안 된다.
  • 경우 3 : 한 번의 꺾기로 첫번째 Puzzle에서 두번째 Puzzle까지 도달 할수 있는지 체크
    • bfs 함수가 true = 한번 꺽기로 도달 가능, false = 한번 꺾기로 도달 불가능
• bfs 함수
  • 꺾은 개수로 정렬해 주는 우선순위 큐를 생성한다.(속도 향상을 위해)
  • 첫 번째 위치에서는 상, 하, 좌, 우를 모두 갈 수 있기 때문에 모든 경우를 우선순위 큐에 넣어준다.
  • BFS 시작
    
    • 만약 count > 2보다 클경우( 꺾기를 2번 이상 했을 경우) 해당 경우는 체크 안 함 = Continue
    • for문을 통해 상, 하, 좌, 우 이동 이때 기존에 출발했던 방향이랑 다를 경우 count를 증가하고 같으면 count증가 안 한다.
      • 한 경우에서 3가지의 경우는 count값이 증가하고 같은 방향(1가지)은 count값 증가 안 시킴
    • 배열 크기보다 작고, 꺾은 횟수가 1회 이하일 때
      • 만약 간 곳이 통과 가능한 곳일 경우 
        • que에 해당 count를 더해주고 방향을 설정해 준다.
      • 만약 간곳이 도착지점일 경우(p2)
        • true를 반환하고 리턴
    • 모든 경우를 하였지만 도착지점을 가지 못할 경우에는 false를 반환한다(while문을 나왔을 때)

• class Puzzle implements Comparable<Puzzle>{ 
      int x; //x좌표
      int y; //y좌표
      char c; //문자
      int count; // 꺾은 횟수
      int dir; //이전 방향
      public Puzzle(int x,int y,char c) { 
          this.x = x;
          this.y = y;
          this.c = c;
      }
      public Puzzle(int x,int y,int dir,int count) { 
          this.x = x;
          this.y = y;
          this.dir = dir;
          this.count = count;
      }
      @Override
      public int compareTo(Puzzle o) {
      	return this.count - o.count;
    	}
  }
  public static int[] dx = {-1,1,0,0};//좌우하상
  public static int[] dy = {0,0,-1,1};
  public static List<Puzzle> list; // 없애야 할 블록 모두 담는다
  public static String solution(int m, int n, String[] board) {
  	StringBuilder answer = new StringBuilder(); // 없앤 블록
      char[][] map = new char[m][n];
      for(int i=0;i<m;++i) {
           map[i] = board[i].toCharArray();
      }
      list = new ArrayList<>();
      initArrayList(map,m,n);//list를 초기화해주는 함수
      for(int i = 0;i<list.size();i+=2) {//사천성을 모든 제거해야 할 문자들이 여기 담겨있다
      	Puzzle p1 = list.get(i);
          Puzzle p2 = list.get(i+1);
          //두 개의 쌍(지울 수 있는지 확인해야 한다)
          if(canRemove(map,m,n,p1,p2)) {
          //지울 수 있다면
          	answer.append(p1.c);//정답에 더해주고
           	list.remove(i);//쌍으로 지운다
           	list.remove(i);
           	map[p1.y][p1.x] = '.';//해당 쌍을 빈 값으로 변경
           	map[p2.y][p2.x] = '.';
           	i = -2;//다시 i는 처음부터 시작
           	continue;
          }
      }
  	return list.size() == 0 ? answer.toString() : "IMPOSSIBLE";//모든 문자를 다 지우면 정답 리턴 , 아니면 IMPOSSIBLE 리턴
  }
  private static boolean canRemove(char[][] map, int m, int n, Puzzle p1, Puzzle p2) {
  	if(p1.x == p2.x) {//같은 열에 존재
        for(int i=p1.y+1;i<=p2.y-1;++i) {//행 탐색하며 
            if(map[i][p1.x] != '.') {//비어있지 않다면 지울 수 없다
              return false;
          }
        }
  		return true;
  	}else if(p1.y == p2.y) {//같은 행에 존재
      	for(int i=p1.x+1;i<=p2.x-1;++i) {//열 탐색하며 
      		if(map[p1.y][i] != '.') {//비어있지 않다면 지울 수 없다
      			return false;
      		}
      	}
  		return true;
  	}else {
  		if(bfs(map,p1,p2,m,n)) {//꺾어서 연결되는지 확인
  			return true;
  		}else {//꺾어서 못 지운다
  			return false;
  		}
  	}
  }
  private static boolean bfs(char[][] map, Puzzle p1, Puzzle p2, int m, int n) {
  	Queue<Puzzle> que = new PriorityQueue <>();//꺾은 횟수를 우선순위로 하는 que
      que.offer(new Puzzle(p1.x, p1.y, 0, 0));//첫 방향에서는 상, 하, 좌, 우 어디로 갈지 모르기 때문에 모두 계산
      que.offer(new Puzzle(p1.x, p1.y, 1, 0));
      que.offer(new Puzzle(p1.x, p1.y, 2, 0));
      que.offer(new Puzzle(p1.x, p1.y, 3, 0));
  	while(!que.isEmpty()) {
          Puzzle p = que.poll();
          if(p.count >= 2) {//꺾은 횟수가 2회 이상이면 계산할 필요 없다
              continue;
          }
          for(int i=0;i<4;++i) {
              int nx = p.x + dx[i];
              int ny = p.y + dy[i];
              int count = p.count;
              if(p.dir != i) {//왔던 방향과 가려는 방향이 다를 경우(꺾었다) count 값 증가
                  count++;
              }
              if(isRange(nx,ny,m,n) && count < 2) { // 만약 꺾은 횟수가 2보다 작고
                  if(map[ny][nx] == '.') {// 갈 수 있는 곳이라면
                      que.offer(new Puzzle(nx, ny, i, count));//BFS 탐색
                  }else if(nx == p2.x && ny == p2.y) {//둘이 만났을 경우
                      return true;// 가능하니까 true 반환 후 함수 종료
                  }
              }
          }
  	}
  	return false;// 모든 경우를 다했지만 1번 이하로 꺾어서는 도착할 수 없으므로 false 반환
  }
  private static boolean isRange(int nx, int ny, int m, int n) {
  	return 0 <= nx && nx < m && 0 <= ny && ny < n;
  }
  private static void initArrayList(char[][] map, int m, int n) {
  	for(int i=0;i<m;++i) {
  		for(int j=0;j<n;++j) {
  			if(Character.isUpperCase(map[i][j])) {//벽과 빈 길이 아닌 사천성을 모든 문자를 넣어준다
  				list.add(new Puzzle(j, i, map[i][j]));
  			}
  		}
  	}
  	Collections.sort(list, (o1, o2)->{//정렬 : 제거해야 할 모든 쓰촨 성 문자를 문자순, (x, y) 좌표가 작은 순으로 정렬한다.
  		if(o1.c == o2.c) {
  			if(o1.x == o2.x) {
  				return o1.y - o2.y;
  			}
  			return o1.x - o2.x;
  		}
  	return o1.c - o2.c;
  	});
  }