BAEKJOON_2206) 벽 부수고 이동하기
BAEKJOON
# 2019 SW역량테스트준비-기초
# 그래프와 BFS # BFS 2
2206) 벽 부수고 이동하기 (19.09.26)
* BFS사용.
* 벽을 하나만 부술 수 있기때문에
* 현재 위치에서 벽을 부순적이 있는지 없는지에 따라서 다음 칸을 선택하는 것이 달라진다.
* 따라서 벽을 부쉈는지 여부로 한 점을 두개의 정점으로 나눠줘야 한다.
* 이때 이전에 부쉈다, 안부쉈다로 z로 판별하면 안됨.
* 현재 칸이 0인지 1인지 확인하고, 그거에 맞게 z를 조건에 넣어줘야함.
* 이번에는 boolean check배열 없이 했다.
* 따로 안만들고, 정답 배열인 ans의 값이 0인지 판별하는 것으로 방문했는지 확인해줬다.
* check 한 거랑 170ms 정도 시간 차이가 남.
* 처음에 그냥 n, m에서 0과 1일때 중에 작은 수로 답을 출력하도록 하고,
* 작은수가 0이면 불가능이라고 판단하고 -1을 출력하도록 했다.
* 근데 1, 1 배열에서 0이 들어가있으면 1을 출력해야하는데 -1을 출력했다.
* 출력 부분을 각각 0인지 아닌지를 확인하는 네 가지 경우를 모두 확인해야했다.
* 벽을 하나만 부술 수 있기때문에
* 현재 위치에서 벽을 부순적이 있는지 없는지에 따라서 다음 칸을 선택하는 것이 달라진다.
* 따라서 벽을 부쉈는지 여부로 한 점을 두개의 정점으로 나눠줘야 한다.
* 이때 이전에 부쉈다, 안부쉈다로 z로 판별하면 안됨.
* 현재 칸이 0인지 1인지 확인하고, 그거에 맞게 z를 조건에 넣어줘야함.
* 이번에는 boolean check배열 없이 했다.
* 따로 안만들고, 정답 배열인 ans의 값이 0인지 판별하는 것으로 방문했는지 확인해줬다.
* check 한 거랑 170ms 정도 시간 차이가 남.
* 처음에 그냥 n, m에서 0과 1일때 중에 작은 수로 답을 출력하도록 하고,
* 작은수가 0이면 불가능이라고 판단하고 -1을 출력하도록 했다.
* 근데 1, 1 배열에서 0이 들어가있으면 1을 출력해야하는데 -1을 출력했다.
* 출력 부분을 각각 0인지 아닌지를 확인하는 네 가지 경우를 모두 확인해야했다.
댓글
댓글 쓰기