프로그래머스 위클리 챌린지 11주차 - java

문제 설명

1. 사각형들이 좌표형식으로 주어진다.

2. 사각형들은 서로 곂치게 놓여지며, 맨 테두리로 욺직일 수 있다.

3. 사람과 아이템이 주어졌을 때, 가장 짧게 아이템을 가져올 수 있는 방법을 구하여라

풀이 과정

// 이거근데 풀었다고 뜨기는 떴는데 다른 테스트 케이스는 통과를 못한다... 아마 정답에 문제가 있는것 같고 나중에 변경해야 할 수도 있다.

// 처음에 풀었을 때에는 22번 테케에서 막히게 되었다. 그 답안은 후첨하겠다.

 

내가 푼 방법은 계속 문제를 생각하다 가장 간단히 구현할 수 있는 방법을 통해 풀었다.

아마 따라하면 쉬운 방법일 테지만, 나중에 답이 틀릴 수 있고 그렇게 되면 변경하도록 하겠다.

 1. 먼저 모든 값을 2배해 준다. ( x축간, 혹은 y축간 거리가 1씩밖에 차이가 안나면 이를 넘어가서 엄청 짧은 루트가 만들어지거나, DFS가 이상하게 돌아서 루트를 엄청 많이 돌게 된다. 이를 방지하기 위함)

 2. 만들어진 도형을 담을 배열을 선언하기 위해 x, y의 최소 최대값을 가져와 boolean형 배열을 만든다.

 3. 모든 도형의 테두리를 true로 받아온다.

 4. 모든 도형의 테두리 내부를 false로 한다.

 -> 이렇게 하면 겹치는 부분의 내부를 없애줄 수 있을 것이라 생각했다.

 5. DFS를 실시한다.

 5-1. 사람이 있는 곳false로 만들어 DFS가 다시 처음을 돌 일을 없애주고 그곳을 기준으로 위, 아래를 stack에 저장한다. 그리고 DFS가 시작되었으니 간 거리를 1로 시작한다.

 5-2. 위아래양옆을 찾아가면서 DFS를 실시한다. 한번 찾은곳은 false로 바꾸어 준다. 이후 item의 위치에 도달하면 내가 걸은 거리를 answer에 저장한다(answer을 최대로 선언 후 한 DFS가 실시되면 둘 중 최소값을 저장해주고 다시 걸은 거리를 1로 변경). 여기서 item의 위치는 절대 false로 변경하면 안된다.

 6. answer을 return하면 된다.

코드

/*

여기서부터는 사족을 좀 달게 될것같다.

틀린 답안의 풀이 과정

// 이거는 틀린 문제인데, 왜 틀렸는지를 모르겠어서 다시 확인해 보기 위해 적는다. 이후 틀린 이유가 밝혀지면 업데이트하겠다. 혹시나 아시는분 있으면 말씀해주세요..

// 요게 22번 테케에서 막히게 되었다. 

 

 1. 먼저 모든 값을 2배해 준다. ('8'모양처럼 가운데가 들어가고 위아래가 나와있는 경우 가운데를 체크하기 위해)

 2. 만들어진 도형을 담을 배열을 선언하기 위해 x, y의 최소 최대값을 가져와 boolean형 배열을 만든다.

 3. x, y의 최소부터 최대값에 걸쳐 도형이 가진 최소값들을 하나씩 저장한다. 예를 들어 4개 도형의 x축이 1 4 6 2이면 최소는1, 최대는 6 이렇게 저장시킨다.

 4. y의 최소~최대까지 값들을 하나씩 점을 찍어준다.

 -> y가 최소, 최대이면 x최소~x최대까지 모든 점을 찍어준다.

 -> 도형의 왼쪽 부분, 즉 x가 최소값인 부분에서는 y최소~y최대-1까지 시행하면서

    현재y축에 해당하는 x최소값과 그 위x최소값을 확인한다.

         현재 y축의 x최소값보다 그 위 x최소값이 크거나 같으면 위에꺼부터 현재꺼까지 그려주기

         현재 y축의 x최소값보다 그 위 x최소값이 작 은 경 우 는 현재 위치의 x최소값에 점찍고 위 라인에 그려주기

 -> 오른쪽 부분은 반대로 시행

 5. DFS를 실시한다.

 6. answer을 return하면 된다.

잘못된 풀이의 코드

 

이렇게 하면 22번을 제외한 모든 테스트 케이스를 통과하는데, 어디가 틀린것인지 감을 못잡는 상태이다...밤새 풀어도 모르겠어서 일단 저장하고 풀이 과정을 남긴 후에 다시 풀어볼 예정이다.

 

여러 방법으로 푸는 문제이며, 구현 방식을 잘못 생각하면 상당히 오래 걸릴 수 있을 것이다.