알고리즘/문제풀이 - 백준

백준 2206 벽 부수고 이동하기

문제 : https://www.acmicpc.net/problem/2206 서론 크게 어렵게 생각 안했는데 시간초과를 연타로 맞았다. DFS로 구현했다가 시간초과 같은 아이디어를 BFS로 구현했다가 시간초과 방문배열을 3차원으로 만들었는데 시간초과 큐에서 꺼낸 후 방문체크에서 꺼내기 전 방문체크로 수정해서 통과 많은걸 얻어가는 문제다. 풀이과정 기존의 이동할 곳이 0이면 방문하고 1이면 방문하지 않는것에서 조건을 하나 추가해준다. 1이더라도 내가 지금까지 벽을 뚫은적이 없다면 벽을 뚫은 후 다시는 벽을 뚫지 않겠다고 공표하고 방문한다. 따라서 방문할때마다 내가 기존에 벽을 뚫었는지 안뚫었는지 확인을 해야하므로 확인할 수 있는 변수를 큐에 좌표와 함께 넣어준다. 여기까지가 내 아이디어였는데 그 후 수많은 ..

2019. 8. 26. 19:13