[백준]_4108번 : 지뢰 찾기(파이썬 and C언어)

4108번: 지뢰찾기

구현이어서 그런가 해야 될 것이 좀 많은 귀찮은 문제들 중 하나이다. 또한 여태까지 푼 문제들 중에서 문제 접근 방법이 파이썬과 C언어가 많이 차이 났던 문제인 것 같다. 먼저 파이썬식으로 전략을 세워보고 C를 위한 디테일은 그 이후에 생각해 보자.

---

전략

파이썬은 어차피 동적 배열이기 때문에 배열의 크기에 대한 걱정은 덜고 시작하는 것이다. 이 문제에서 가장 걸리는 것은 *을 어떻게 처리해야 그 주변 값들이 하나씩 증가할 것이냐 이다. 그래서 일단 다음과 같은 함수들을 만들어주기로 하자.

 

user() : 사용자가 게임판을 입력하고 그 입력값을 2차원 배열에 대입

find() : 우리의 유일한 관심사인 *의 좌표를 찾아서 add함수로 전달

add() : find에서 전달받은 좌표들을 토대로 *주변의 원소들의 값을 1 증가시켜줌. 단 1증가 적용 위치가 게임판을 넘어가지 않게 조심해야 함. 잘못하면 인덱스 에러를 일으킬 수 있음.

show() : 개조가 완성된 게임판을 출력

 

---

일단 user와 find, show는 쉽게 구현이 가능하기 때문에 본체(main)와 함께 일단 만들어주자.

import sys
input=sys.stdin.readline
# 입력
def user():
    for i in range(R):
        row=input()
        for j in range(C):
            if row[j]=='.':
                pan[i].append(0)
            else:
                pan[i].append('*')
# 지뢰 찾기
def find():
    for r in range(R):
        for c in range(C):
            if pan[r][c]=='*':
                add(r,c)
# 지뢰 주변 값 변화
def add(??):
    <아직 몰라!!>

# 출력
def show():
    for r in range(R):
        for c in range(C):
            print(pan[r][c], end='')
        print()

# 본체
while 1:
    R, C = map(int, input().split())
    if R + C == 0:
        break
    pan = [[] for _ in range(R)]  # 열의 크기가 지정 안된 2차원 배열 생성
    user()
    find()
    show()

깨알 스킬로 show 함수에서 end=''를 깨주기 위해서 print()를 사용한다.

이제 add함수를 생각해 주자. 앞서 언급했듯이 add함수로 인자 두 개가 전달된다. 바로 *이 있는 위치의 행과 열 정보인데, 우리가 알기 편하게 행 정보를 y, 열 정보를 x로 받자.

이제 지뢰 주변을 검사하기 위해서는 x, y에 +1, +0, -1 등 조합을 통해서 주변을 1 증가시켜 준다. 하지만 인덱스 에러를 피하기 위해서는 다음과 같은 조건을 추가로 고려해주어야 한다.

 

0 <=y+y_<R and 0 <=x+x_<C // 이때 x_, y_은 -1, 0, 1중 하나이다.

 

따라서 최종 코드는 다음과 같다.

시도 1(Python)

import sys
input=sys.stdin.readline
# 입력
def user():
    for i in range(R):
        row=input()
        for j in range(C):
            if row[j]=='.':
                pan[i].append(0)
            else:
                pan[i].append('*')
# 지뢰 찾기
def find():
    for r in range(R):
        for c in range(C):
            if pan[r][c]=='*':
                add(r,c)
# 지뢰 주변 값 변화
def add(y, x):
    for y_ in range(-1, 2):
        for x_ in range(-1, 2):
            if 0<=y+y_<R and 0<=x+x_<C and pan[y+y_][x+x_]!='*':
                pan[y+y_][x+x_]+=1

# 출력
def show():
    for r in range(R):
        for c in range(C):
            print(pan[r][c], end='')
        print()

# 본체
while 1:
    R, C = map(int, input().split())
    if R + C == 0:
        break
    pan = [[] for _ in range(R)]  # 열의 크기가 지정 안된 2차원 배열 생성
    user()
    find()
    show()

---

시도 2(C언어)

#include <stdio.h>
int R,C;
int pan[100][100];
void user(void);
void find(void);
void add(int, int);
void show(void);
int main() {
    while(1){
        scanf("%d %d",&R, &C);
        if(R+C==0) break;
        user();
        find();
        show();
    }
}
void user(void){
    for (int i = 0; i < R; ++i) {
        char arr[C];
        scanf("%s",arr);
        for (int j = 0; j < C; ++j) {
            if(arr[j]=='.') pan[i][j]=0;
            else pan[i][j]='*';
        }
    }
}
void find(void){
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if(pan[i][j]=='*') add(i,j);
        }
    }
}
void add(int y, int x){
    for (int y_ = -1; y_ < 2; ++y_) {
        for (int x_ = -1; x_ < 2; ++x_) {
            if(0<=x+x_ && x+x_<C && 0<=y+y_ && y+y_<R && pan[y+y_][x+x_]!='*') pan[y+y_][x+x_]+=1;
        }
    }
}
void show(void){
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if(pan[i][j]==42) printf("*");
            else printf("%d", pan[i][j]);
        }
        printf("\n");
    }
}

파이썬과 달리 지역 변수와 전역 변수의 개념이 존재하기 때문에 R, C, pan [][]을 전역 변수로 설정해 주었다. 또한 malloc을 사용한 pan의 동적 할당도 고려해 보긴 했지만 귀찮아서 그냥 게임판의 최대 크기인 100으로 설정하고 필요한 부분들만 다루는 전략으로 바꿨다. 

 

마지막으로 가장 골치 아팠던 것은 *을 int형 pan에 저장하려고 하니까 *의 아스키코드 값인 42를 저장하는 것이다.. 따라서 생각해 낸 꼼수는 그냥 42가 저장되어 있는 칸을 출력할 때는 *을 출력하도록 한 것이다. 여기서 들 수 있는 의문은 42가 아니라 주변에 진짜로 지뢰가 42개 있으면 어떻게 하냐?이다. 사실 걱정할 필요가 없는 이유는 주변에 존재할 수 있는 지뢰는 많아봤자 8개이기 때문이다.