[BOJ14466] 소가 길을 건너간 이유 6

14466번: 소가 길을 건너간 이유 6

1. 내 위치를 기준으로 다음 위치로 가는 곳이 '길'인 경우를 판단해야 함

   - 길의 좌표가 주어질 때 좌표를 기준으로 어느 방향이 길인지를 체크한다.

   - boolean map[N+1][N+1][4] 의 형태로 정방향과 역방향을 표시한다.

   - 역방향 표시는 reverse[] 배열을 이용한다.

 

2. 소의 위치를 저장시킬 배열 boolean positionOfCow[N+1][N+1]

 

3. bfs는 소의 수 만큼 실시(K번)

   - 소의 위치를 기준으로 갈 수 있는 곳을 4방탐색하여

   - 정해둔 if문을 넘어가는 경우만 다음 곳으로 갈 수 있게 한다.

 

// 주석 파일 참고

/*
1. 길의 표시
    특정 위치 (x,y)에서 인접한 4 방향 중 다리가 연결될 것.
    그러면, map[N+1][N+1][4]의 꼴로 내 위치 기준으로 어느 방향으로 가는 곳에 길이 있는지, 
    다음 위치에서도 길이 어느 방향인지 파악.
    boolean map[N+1][N+1][4] 필요

    []xDirection = {-1,0,1,0};
    []yDirection = {0,1,0,-1};
    (2,2)를 기준으로 4방은 (1,2) (2,3) (3,2) (2,1)

    (1,2) 기준 (2,2)가 되려면 2
    (2,3) 기준 (2,2)가 되려면 3
    (3,2) 기준 (2,2)가 되려면 0
    (2,1) 기준 (2,2)가 되려면 1
    즉 []reverse = {2,3,0,1}



    2. 소의 위치 & 소 배열 선언
    소의 수를 담을 배열 Coordination cowArr[K]
    소의 위치는 boolean positionOfCow[N+1][N+1]

    3. 알고리즘 - bfs
      1) 소의 수 만큼 bfs 실시
        가) Queue, boolean visited[N+1][N+1]
        나) 예외조건
            1) 범위 안에 안들어와있거나, visited[nx][ny]인 경우
            2) 어느 방향으로 나아가려 하는데 그게 길인 경우

        다) cnt 증가 조건
            1) 다른 소를 만난 경우 cnt 증가

        위의 경우가 아니면 방문처리 후 큐에 삽입.


     */​

 

https://github.com/ssjjaa-algo/AlgoAndMySQL/blob/master/src/Baekjoon/BOJ14466.java