알고리즘 with Swift (7569 tomaoto)

알고리즘 스터디가 드디어 두둥 열렸기에 빠질수 없어 보자마자 참여.

첫 문제로는 토마토 문제. 

어디선가 봤던 유형인데 알고리즘을 안푼지가 백만년이라 역시나 감도 안온다....

일단 읽으면 어? 근처에 있으면 옮아? 옮고 또 그것은 다른것에 영향을 끼친다고?라고 생각하니까 이건 무조건 BFS로 해야겠다를 먼저띵킹

1. 1트 ( 시간초과)

1

임시 샘플들을 넣으면 결과값이 제대로 나오지만 시간초과가 뜬다. 왜지? 

내가 생각한 풀이는 처음에 1인 지점에서 위,아래, 왼.오. 앞,뒤 로 전염이 되기에 먼저 위아래를 제외한것들을 먼저 전염시키고 그 두 if문에서 row가 N만큼 더 가서 그 지점도 0이라면 감염시키고 큐에 넣어주는 형식으로 구현하였다.

찾아보니 removefirst는 시간복잡도가 O(n)이라 생기는 문제였다. 그래서 index라고 포인터를 만들어 +1 해가며 다음걸로 가는 형식으로 짯는데 테스트 예제들은 모두 통과를 하였으나 채점결과 틀.렸.습니다가 떠버림..아놔 그래서 반례를 찾기시작.

하지만 다른 반례들도 다 정답이 뜨는데 뭐가 문제읹지 모르겠음.

아 찾응. 저 위에 사진으로 2번 인덱스에서 만약 감염이 이루어지면 3번 인덱스도 전염이 이어진다. 하지만 구조상 우리는 왼, 오, 앞, 뒤, 위, 아래만 가능해야하기에 오류가 뜬 것이였다.(룸메이트가 도와줌)

가독성도 구리다는 피드백을 받아서 바로 3차배열로 짜기시작.

그래서 나온 결과물!! 이번에는 통과를 하였다.

box를 삼차배열로 만들고 첫번째에는 위층 아래층을 구분해주고 그 뒤는 같게 진행을 하였다. 그러다 보니 위 코드랑 달리 N*h등 임의로 구해줄 필요가 없어 코드가 훨씬 짧아지고 마지막은 마찬가지로 flatMap을 써서 일차배열로 바꾼뒤 구해주었다. 3차배열쓰기 싫어서 다른 방법을 사용해봤지만 돌고돌아 삼차