yunbinni   1년 전

상하좌우 4방향씩 개별로 테스트할 때는 문제없이 잘 되어지는데,

DFS로 돌리기만 하면 다른 답을 내놓습니다.

문제에서 주어진 테스트케이스 중 1, 5, 7번을 입력하면 그렇습니다.


제가 생각한 풀이 중 위로 기울이는 함수를 예로 들면..

bool R빠졌는지=false, B빠졌는지=false;
int res; //R은 빠지고 B는 안빠졌는지

...

[여기는 네임스페이스]

char arr[14][14];

위로 기울이는 함수:
    열마다 탐색:
        행마다 탐색:
            만약 좌표가 R이나 B라면:
                임시변수 mrbl에 R이나 B를 담는다;
                그 자리를 '.'으로 채운다;
                현재 행 인덱스를 임시변수 pos에 저장한다;
                위쪽으로 이동할 수 있을 때까지 pos를 위로 올린다;
                만약 'O'를 발견한다면:
                    R이면 R빠졌는지=true;
                    B이면 B빠졌는지=true;
                'O'가 아니라면: arr[pos][j]=mrbl;

...

DFS는 움직일 방향을 지정해주는 함수,
깊이가 10이 되면 움직인다(solution함수 호출)

solution:
    입력받은 문자를 네임스페이스의 arr에 복사한다.
    1부터 10까지 i 반복:
        만약 res가 1이라면 return;
        
        움직임이 지정된 배열(bit[i])에 따라 기울인다.
        bit에는 0~3까지 있으며,
        0이면 위, 1이면 아래, 2이면 왼쪽, 3이면 오른쪽으로 기울인다.

        만약 R은 빠지고, B는 안빠졌다면: res=1;

main함수:
    입력받는다;

    DFS를 돌린다(10이되면 solution 호출);

    res를 출력한다;

    끝;

이런 식으로 풀었습니다.

그래서 움직임을 DFS로 하지 않고

그냥 한번만 움직이면 res에도 잘 반영되는데, (테스트케이스 1번을 오른쪽으로 한번만 움직인다면 res는 1이 됩니다.)

DFS를 타면 왜 잘 안되는지 모르겠습니다.

yunbinni   1년 전

DFS는 4방향 모두 구현해야하고,

R과 B의 선후순서를 따져야 하기때문에 오류를 낼 확률이 높다고 합니다.

따라서 이 문제는 BFS로 풀어야 효율적으로 코딩할 수 있습니다.

정말 좋은 풀이를 공유하고자 합니다.

저는 거의 베끼다시피 풀었지만,,나름 함수형으로 고쳐썼다고 핑계를 대봅니다.

여기

댓글을 작성하려면 로그인해야 합니다.