[코드트리] 체크판위에서 2 /완전탐색, 2차원배열

 

https://www.codetree.ai/missions/5/problems/on-the-checkboard-2?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

체크판위에서 2

---

 

 

입출력 예제

 

입력

5 5
W W W W W
W W W W W
W B W W W
W W W W W
W W W W B

 

출력

2

 

 

문제

R * C 크기인 직사각형의 각 칸이 W, B로 표현되어 있습니다. W는 하얀색으로, B는 검은색으로 칸이 채워져 있는것을 뜻합니다. 왼쪽 상단에서 출발하여 우측 하단으로 이동할 때, 특정 룰을 만족하면서 이동에 성공할 수 있는 경우의 수를 구하는 프로그램을 작성해보세요. 아래가 특정 룰입니다.

1. 이동은 항상 점프를 통해서만 가능합니다. 또, 점프 진행시 항상 현재 위치에 적혀있는 색과, 점프한 이후의 칸에 적혀있는 색이 달라야만 합니다.
2. 점프 진행시 현재 위치에서 적어도 한칸 이상 오른쪽에 있는 위치이며 동시에 현재 위치에서 적어도 한칸 이상 아래쪽에 있는 위치인 곳으로만 점프가 가능합니다.
3. 정확히 시작, 도착 지점을 제외하고 점프하며 도달한 위치가 정확히 2곳 뿐이어야 합니다.

 

우선 문제를 읽었을때 R이 세로 C가 가로이므로 R은 행의 수 C는 열의 수이다. 

1. 이를 우선적으로 공백으로 입력 받는다. : R, C = tuple(map(int, input().split())

2. 격자판을 만들기 위해 2차원 배열을 입력 받는다 : arr = [ input().split() for _ in range(R) ] 

   - 공백으로 잘라서 한 줄 입력받고 이를 R행 반복해서 배열에 담는다.

3.  이동은 점프로만 가능한데 점프시 색이 달라져야한다. 인덱스 (0,0) 칸에서 시작해서 (R-1, C-1) 로 도착하여야한다. / 점프 시 오른쪽과 아래쪽에 위치하여야한다. 만약 내 위치가 (i, j) 라면 행의 수가 커지고 열의 수가 커져야 한다. i+1부터 행 순회 j+1부터 열 순회해야함 /

정확히 시작, 도착 지점을 제외하고 점프하며 도달한 위치가 2곳뿐이어야한다.

4. 따라서 처음 순회는 내 위치이다. 주의할 점은 (0,0)은 이미 밟았음을 가정하므로 

for i in range(1, R):

     for j in range(1, C):

로 인덱스 (1,1)부터 밟아야한다.

 

내가 다음 뛸 수 있는 곳을 또 탐색한다.

for k in range(i+1, R-1):

    for l in range(j+1, C-1):

를 통해 순회한다. 행 열 둘다 현재 위치보다 더 크게 순회해야하므로 i+1, j+1 부터로 각각 인덱스 설정을 한다. 마지막으로 뛸 곳은 arr[R-1][C-1] 이어야하므로 이는 제외한다.

 

다음은 조건에 맞게 확인하는 것이다. 

arr[0][0] != arr[i][j] 이면서 arr[i][j] != arr[k][l] 이면서 arr[R-1][C-1] != arr[k][l] 이여야한다

이것은 (0,0) 에서 출발해서 (R-1, C-1) 로 도착해야하는데 두번의 경유지를 지나야하는데 이때 행수는 늘어나고 열수도 늘어나는 곳으로만 이동할 수 있다. 또 같은 색으로는 뛸 수 없다. 같은 색이 아닌 조건에 맞는 수를 카운트해준다.

 

 

 

 

코드

R, C = tuple(map(int, input().split()))
grid = [
    list(input().split())
    for _ in range(R)
]


cnt = 0
for i in range(1, R):
    for j in range(1, C):
        for k in range(i + 1, R - 1):
            for l in range(j + 1, C - 1):
                
                if grid[0][0] != grid[i][j] and \
                   grid[i][j] != grid[k][l] and \
                   grid[k][l] != grid[R - 1][C - 1]:
                    cnt += 1
                        
print(cnt)

 

 

알게된 사실 :

1.  2차원배열 선언할 때

    arr  = [ list(input().split()) for _ in range(R) ] 로 처음에 리스트를 만들고 이를 반복하는 방식으로 했는데 리스트 안써줘도 됨

    arr = [ input().split() for _ in range(R) ] 로만 써도 된다.