코딩도장 : 연습문제(지뢰찾기)

지뢰찾기 알고리즘

 

https://dojang.io/mod/quiz/view.php?id=2298

코딩 도장: 사이트에 로그인

 

1. 표준 입력으로 2차원 리스트의 가로와 세로를 입력한다.

2. 그 다음 줄부터 리스트의 요소로 들어갈 문자가 입력된다.

3. 2차원 리스트 안에서의 * 는 지뢰이고 . 은 지뢰가 아니다.

4. 지뢰가 아닌 요소에는 인접한 지뢰의 개수를 출력하는 프로그램을 만들어라.

 

기본으로 제공되는 코드

matrix = []
for i in range(row):
  matrix.append(list(input()))

 

연습문제를 순서대로 풀면서 가장 난이도가 높았던 문제이다. 2차원 배열을 처음 접하면 2시간 정도는 걸릴 수도 있다고 하는데,

실제로 문제를 풀면서 2시간은 훌쩍 넘겼다.

 

지뢰 개수를 검사하는 알고리즘을 짜기 전에 기본적으로 아래와 같이 2차원 배열을 만들었다.

row, col = map(int, input().split())
matrix = []
for i in range(row):
    matrix.append(list(input()))

print(matrix)

'''
# row, col 입력 값
3 3

# list(input()) 의 입력 값, row 로 반복문을 입력하고 있기 때문에 3줄 까지 입력 가능하다.
..* 
.*.
...

# print(matrix) 결과 값
[['.', '.', '*'], ['.', '*', '.'], ['.', '.', '.']]
'''

여기서 실수했던 점은 list(input()) 이 아닌, [input()] 를 사용했었다는 것인데,

[] 안에 input() 을 사용해서 값을 받으면, 리스트 안에 들어가는 요소가 1개가 되어버린다.

반면 list() 내장 함수를 이용하면, 입력한 값이 string (반복가능한 값) 이기 때문에 입력한 값이 각각 요소가 되어 들어가

2차원 배열의 형태가 된다.

위의 결과 값에서 matrix[0][2] 를 찍어보면 * 가 나온다.

 

또한, 한 줄에 입력한 요소의 문자열의 길이가 3개가 넘을 경우, 이 다음 코드로 row, col 의 2중 반복문을 돌려서

알고리즘을 짤 때 검사하지 못하는 요소가 생길 수가 있다. (for in range(row) 로 반복문을 썼기 때문에)

하지만 이 부분은 일단 넘어가도록 하고 일단 정확하게 입력하도록 했다.

 

지뢰 개수를 카운팅하는 핵심은 (다른 방법도 많겠지만..) * 가 아닌 문자열, 즉 문자열 . 가 있는 인덱스를 기준으로 근처 8 곳의 인덱스

왼쪽 위, 위, 오른쪽 위, 왼쪽, 오른쪽, 아래 왼쪽, 아래, 아래 오른쪽

의 값이 * 일 때 카운팅 시켜주는 것이다. 이 원리만 파악하는데 1시간은 쓴 것 같다.

 

 

제출 코드

row, col = map(int, input().split())
matrix = []
for i in range(row):
    matrix.append(list(input()))
    
searchIndex = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]

for i in range(row):
    for j in range(col):
        if matrix[i][j] == "*":
            continue
        elif matrix[i][j] == ".":
            count = 0
            for x, y in searchIndex:
                if (0 <= i+x <= row-1) and (0 <= j+y <= col-1):
                    if matrix[i+x][j+y] == "*":
                        count += 1
            matrix[i][j] = count
for i in range(row):
    for j in range(col):
        print("".join(str(matrix[i][j])), end="")
    print()

searchIndex 라는 2차원 리스트를 만들고, 그 안에 * 가 들어있는 인덱스 8곳의 상대적 인덱스 위치 값을 저장하였다.

즉, 기준 값 matrix[1][1] 에서 왼쪽 위의 인덱스는 1 + -1, 1 + -1 이 되서 matrix[0][0] 이 되도록 하고, 그 안의 값이 * 라면

matrix[1][1] 는 카운트 변수 1 을 올려서, 그 카운트 값을 저장하도록 하였다.

출력할 때는 matrix 안에 값이 카운트 변수로 인하여 int 가 되어있기 때문에 join() 부분에서 에러가 나는 것을 방지하기 위해

str() 내장 변수로 문자열로 변환시켰다. 하면서 시행착오가 정말 많았던 문제였다.

 

문제를 제출 한 뒤 도움말 부분을 참고하면 굳이 searchIndex 라는 리스트를 만들지 않아도 되었다.

row, col = map(int, input().split())
matrix = []
for i in range(row):
    matrix.append(list(input()))
for i in range(row):
    for j in range(col):
        if matrix[i][j] == "*":
            continue
        else:
            count = 0
            matrix[i][j] == 0
            for searchRow in range(i-1, i+2):
                for searchCol in range(j-1, j+2):
                    if searchRow < 0 or searchCol < 0 or searchRow >= row or searchCol >= col:
                        pass
                    else:
                        if matrix[searchRow][searchCol] == "*":
                            count += 1
            matrix[i][j] = count
for i in range(row):
    for j in range(col):
        print("".join(str(matrix[i][j])), end="")
    print()

 

2차원 배열은 연습이 더 많이 필요하다고 느꼈다.