2019년 3월9일 삼성 코테 A형 후기

한 문제만 풀자는 식으로 1번 버스 운전사부터 풀었다.

DFS로 굉장히 명확한 문제였는데,

좀 더 유연하게 생각을 못 했다.

문제는 버스가 → ↓ ↘ 총 세 방향으로만 갈 수 있다.

단, 가로 세로인 상태에서는 한칸을 더 가서 비틀어야 한다. 그래서 총 4칸이 비어있어야 한다.

또한 이미 버스가 대각 상태에서는 가고자 하는 방향에 벽만 없다면 따로 조건을 확인할 필요가 없다. 왜냐하면 대각상태로 올 수 있다는 것은 4칸이 모두 비어있다는 뜻이기 때문이다.

모두 if문으로 구분하여 dfs를 돌렸다.

가로 -> 가로 직진

세로 -> 세로 직진

가로 -> 대각

세로 -> 대각

대각 -> 대각

대각 -> 가로

대각 -> 세로

2가지 부족한 점을 정리해보자면,

1.  도착 시, 버스는 가로 또는 세로로 도착해야 한다.

시작, 도착 시에는 세로 또는 가로로만 시작, 출발할 수 있다.

(시작시에는 가로 또는 세로 두 가지 경우로 나눠서 dfs돌려서 누적)

이동하여 종료좌표에 이르렀을 때, 대각상태이면 안 된다.

나는 이 처리를 대각->대각 직진의 경우의 조건 처리에서 이동한 좌표가 N-1&&N-1이면 처리하지 않도록 하였다.

- 일단, 이렇게 할 경우 다른 가로->대각, 세로->대각인 경우에 대해서 따로 처리해야 하는 단점이 있다.

이것을 단순하게 하려면 기저조건에서 모두 처리하면 된다. dfs 함수 도입부에서 기저조건을 설정(종료 좌표)하고 상태가 대각상태면 그냥 return하면 된다.

2. 대각으로 회전하기 위해서 주변 3칸을 확인할 때, if 문 안에서 중첩 if문의 조건을 만족하면 바깥 if 를 빠져나가기만 해야하는데, 아예 return 해버리는 실수를 범하였다.(이렇게 다면, 아래 모든 가능한 dfs는 수행하지 못 하게 된다.)

ex. 

나의 틀린 풀이(※매번 실수하는 부분!!! 이번에 당했으니 영원히 기억남겠지..)

if(st == 0 && dr[i] == 1 && dc[i] ==1){

for(int j = 0 ; j < 3; j++){            

if(map[r+dr[j]][c+dc[j]])            // 이 조건을 한번이라도 걸리면 dfs를 수행안하고 if문 탈출!

return;                 <- 땡!      <- if문만 빠져나가게 해야 함, if문 아래의 다른 조건문들을 수행해야할 때

}

dfs()

}

if(st == 0 && dr[i] == 1 && dc[i] ==1&&map[nr][nc]==0){

bool check = false;

for(int j = 0 ; j < 3; j++){            

if(map[r+dr[j]][c+dc[j]])            // 이 조건을 한번이라도 걸리면 dfs를 수행안하고 if문 탈출!

check = true;           

}

if(check!=true)

dfs()

}