Tempo Tempo

생각한것들 간단한 백트래킹 문제였다. 백트래킹 체크 부분도 그다지 어렵지 않았는데.. 자그마한 실수 때문에 풀이 시간이 정말 많이 늘어났던 문제다. 실수 백트래킹 체크 부분을 지난 후, 버려야 할 분기임에도 다음 좌표로 넘어가게되어 무한루프에 빠지는 경우가 생겼다. 0인 칸에 1~9까지의 가능한 숫자들을 넣어보고(반복문) 가능한 숫자가 존재하지 않으면 반복문을 종료해야하는데, 2중 반복문인것을 간과하고 한 개의 반복문만 종료시킨게 실수였다. 문제 풀이 간단하게, 9*9 map을 돌면서 0인칸이 나오면 숫자가 들어가있지않은 칸이기 때문에, 1~9까지 넣어보며 가능한 값을 찾는다. 가능한 값이 존재하지 않을 경우, 해당 분기를 버린다. package backjoon; import java.io.*; impo..

생각했던 것 문제의 모양을 보고 바로 BFS 문제라고 생각했다. 다만, 생각없이 visited 처리를 넣는 바람에 시간이 많이 걸렸다. 문제의 키 포인트는 "벽에대한 처리"와, xor를 이용한 "동전이 하나만 떨어졌을 때의 감지"이다. 추가적으로, 최소해를 찾기 위해서는 각 순회마다 따로 count를 세어줘야한다. (재귀를 사용한다면, 메소드의 파라미터에 count를 넘겨주므로 신경쓰지 않아도 됨) 나는 bfs를 반복문으로 구현했기 때문에, 각 순회마다 따로 count를 세어주었다. ++ 예전에 풀었던 7576 - 토마토 문제에서는, count를 기록해주는 배열을 따로 만들어두었다. 해당 문제에서는 벽이 없었기 때문에, 해당 방식으로 저장 할 수 있었던것 같다. 실수 4방향 BFS에서 visited는 당..

같은 코드로도 두 문제를 모두 통과 할 수 있어서 묶어서 올리게 되었다. 생각했던 것들 일반적인 순열 문제라고 생각해서, 처음에 Input으로 들어오는 연산자들의 개수만큼 ArrayList에 넣어 둔 후, 순열로 돌면서 선택하는 방법으로 구현했다. ex) 연산자의 개수가 각각 + : 1, - : 2, * : 3, / : 4 개일 경우, 연산자 각각의 인덱스를 이용해 모두 삽입 ArrayList -> {0, 1, 1, 2, 2, 2} 와 같이 만들어두고 연산을 진행했다. 해당 코드로 연산자 끼워넣기 (1)을 통과하고나서, (2)도 똑같은 방식인것 같아 같은 코드를 넣었더니.. 오랜만에 보는 시간 초과 메세지가 보였다. 틀린 이유 틀린 이유는 생각보다 간단했다. 위의 코드에서, + 연산자를 두 번째로 선택한..