알고리즘 문제풀이 [#4] 코딩도장_지뢰찾기 이야기

코딩도장의 경우 문제 밑에 이미 해답지가 다 있어 저도 올리지만,

문제를 한번  풀어주신 분만 밑으로 봐주시길 바랍니다.

 

문제 설명 이후에 답안 나옵니당.

지뢰찾기 게임은 M x N 매트릭스에 위치해 있는 지뢰를 찾는 게임이다.

M x N 매트릭스 상의 격자(square)는 지뢰이거나 지뢰가 아니다.

지뢰 격자는 *로 표시한다. 지뢰가 아닌 격자(square)는 숫자로 표시하며 그 숫자는 인접해 있는 지뢰의 수를 의미한다. (격자(sqaure)는 최대 8개의 인접한 지뢰를 가질 수 있다.)

다음은 4x4 매트릭스에서 2개의 지뢰(*)를 표시하는 방법이다.

*... .... .*.. ....

이 게임의 목표는 지뢰의 위치(*)를 제외한 나머지 격자들의 숫자를 맞추는 것이다.

위 경우의 답은 아래와 같다.

*100 2210 1*10 1110

입력

첫번째 줄은 M x N 의 M(행)과 N(열)에 해당되는 숫자이다. N과 M은 0보다 크고 100 이하이다. (0< N, M <=100) 그 다음 M개의 줄이 차례로 입력되고 각 줄은 정확하게 N개의 문자가 입력된다. 지뢰 격자는 *로 표시하며 지뢰가 아닌 격자는 .(dot)로 표시한다.

출력

지뢰(*)를 제외한 나머지 격자의 숫자값을 찾아서 M x N 매트릭스를 출력한다.

---

예1)

입력

4 4 *... .... .*.. ....

출력

*100 2210 1*10 1110

---

예2)

입력

3 5 **... ..... .*...

출력

**100 33200 1*100

 

http://codingdojang.com/scode/421

코딩도장

 

 

=======================================================

 

1) 지뢰찾기 문제를 시작하다

 

이 글의 시작은 주변에 알고리즘 문제를 하나씩 풀어보는 지인개발자가 있어서..

어쩌다보니 저도 풀게 되었던 것이죠

 

(아 혹여.. 코딩테스트 문제같은 경우는 그냥 즉석에서 생각나는 개념만 얘기하지

실제 코드레벨의 이야기는 하지 않았습니다. 요런 문제 같이 풀기도하다가
아시는 분 회사의 문제풀기도해서.. 코드레벨까지 이야기하게 되면 그 아시는 분한테 실례다보니;;)

(항상 쉬운 것같아요로 시작하지만 피를 토하곤 합니다. ) 

 

이 글은 지난 번 다리를 건너는 트럭의 글 ( https://adunhansa.tistory.com/322 )과 같은 성격으로

제가 한번 먼저 풀어보고, 저는 이런 개념으로 풀 것같네요 하고서

신입시절에 제 옆자리로 왔던 개발자분에게 의식의 흐름(?)대로 쓴다는 생각으로 적어보도록 하겠습니다.
(문제풀이 이야기 적기를 좋아하다보니..;)

 

2) 까임방지의 글

개발자 월드에서는 코드를 깎는 것이 아니라, 다른 사람을 깎으며 고양감을 충족시키는 모습을 가끔 보기도 합니다..

물론 올바른 코드, 에러, 잘못된 내용에 대한 수정은 있어야 하겠지만,

개발의 세계에서 가장 중요한 것은 개발이라는 것에 대한 흥미를 잃지 않는 것이라고 생각합니다. 

 

글을 쓰는 사람도, 논평을 하는 사람도 처음엔 개발에 대한 흥미가 생겨서 시작을 했던 것이 아닐까요..?

그렇다면 남들에 대한 그 흥미도 충분히 생각하고 상호존중해야 된다고 생각합니다.

잘못된 내용이 전파되는 것보다 더 나쁜 것은 상대방의 개발과 글쓰기에 대한 흥미를 떨어뜨리게 만드는 행동이라고 생각합니다.

 

아 저도 지뢰찾기를 풀어보면서 나의 문제풀이는 달라, 나의 문제풀이는 특별해.. 후후

이런 마음의 함정이 제 속에서도 존재함을 알기 때문에 적어보는 부분이기도 하겠습니다만

모든 방법은 다 나름의 가치가 있고 다양성의 세계는 중요하다고 생각합니다. 

 

잡설이 길으니, 문제풀이로 가보자면.. 

 

 

3) 문제풀이의 도출

자 그래서 문제를 만났을 때 , 이게 결국은 핵심이 지뢰찾기에서 지뢰위주로 숫자들이 올라가져야한다는 것이어서.. 

세세한 구현에 앞서 크게 세가지의 모습을 그려봅니다. 

 

3-1) 역시 첫생각은 2중for문이지 하고서 설명했던 그림

2중 포문을 그리고 하나를 위치를 기준으로 주변을 그리는 모습이 역시 바로 생각났던 것같기도하고..

3-2) 뭔가 9가의 수를 한번에 보는 느낌.. ?

 

그냥 9개의 수를 한번에 읽는 큰 눈을 가진 존재(?)를 상정해서 돌릴까도 생각해봤는데 이게 뭐 결국은 위에랑 같은 구현일 듯하여 패쓰..

눈을 동시에 떠서 9개쯤은 간단히 봐야..

 

3-3) 지뢰를 기준으로 주변의 숫자들을 1씩 올리는 방법

 

( 아 코드없이 개념만 얘기해봤는데, 너무 설명을 많이 한 것인가 싶기도 ;; )

저의 결론은 3번으로 났습니다. 

왜냐하면 지뢰찾기에서 한 칸한칸 일일이 다 옮기면서 또 다시 주변의 지뢰를 탐색한다는 것은

M*N 이 커질수록 처리해야할 일이 많아지기 때문이죠 ( 아 근데 한번 도는 거밖에 없구나. 흠.. ;; ) 

빅오표기법같은 것은 기억이 가물가물하지만...이정도는.. 느낌적 느낌으로
지뢰를 기준으로 찾는것이 빠를 것같다는 결론이.. ( -ㅅ-)a 

 

4) 같은 개념 그리고 다른 코드.. 

그래서 이 지뢰찾기에서의 핵심부분은 지뢰를 기준으로 주변탐색을 하는 것인데, 

왼쪽으로 이동할 때는 자신의 인덱스 숫자에서 -1 을 하면 되고

오른쪽은 +1 

위로갈때는 가로사이즈 -5

밑으로 내려갈때는 가로사이즈 +5 로 하면 주변의 위치로 이동을 할 수가 있다는 것이죠

 

 

그런데 문제는 가장자리 이기 때문에 15의 경우 가로사이즈 5로 나누면 나머지가 0 이므로

가로사이즈로 나눴을 떄 나머지가 0인 숫자들은 왼쪽으로 이동을 못하게 되고

나머지가 4인 숫자들은 오른쪽 이동을 못하게 됩니다. 

 

아는 지인분께는 뭐 이런 위치탐색정도의 개념을 설명드리니 다음과 같은

물어보고  ( isPossible ) 

이동혹은 계산한다 ( calculrate )

라는 도식을 가져오셨습니다 ^0^

 

개발에서의 재미라고 할 수 있는 부분이 같은 개념과 정말 다양한 해답이 있어서 재미가 있는 것은 아닐까 합니다만

public interface CalculateStrategy {
    int MIN = 0;
    boolean isPassable(int mineNumber);
    int getCalculateNumber(int mineNumber);
}

이런 각각의 이동에 대하여 전략패턴으로 구성을 해오셨더라구요~

각각의 이동을 전략패턴으로 구성하면 게임의 난이도를 동적으로 바꿀 수도 있기 때문에

괜찮은 접근이라고 생각하였습니다. 

 

 

 

전략패턴에 대한 링크를 잠시.. 

https://victorydntmd.tistory.com/292

[디자인패턴] 전략 패턴 ( Strategy Pattern )

그렇다면 코딩도장에 적은 제 쪽의 구현코드는 다음과 같습니다. 

아 우선 지뢰찾기의 한 칸을 Block 이라고 명명하겠습니다. 

그리고 index 는 각자 자기자신의 숫자이고, width 는 가로길이입니다. 

( rowNum 같은 명명도 좋지 않나 싶지만..  width 는 제가 친숙해서입니다. [퍽])

enum MovingStrategy {
        UP(b -> b.getBlock(b.getIndex() - b.getWidth())),
        DOWN(b -> b.getBlock(b.getIndex() + b.getWidth())),
        LEFT(b -> {
            if (!b.isInGameBlock()) return b;
            int index = b.getIndex();
            if (index % b.getWidth() == 0)
                return Block.OUTOFGAME;
            return b.getBlock(index - 1);
        }),
        RIGHT(b -> {
            if (!b.isInGameBlock()) return b;
            int width = b.getWidth();
            int index = b.getIndex();
            if (index % width == (width - 1)) {
                return Block.OUTOFGAME;
            }
            return b.getBlock(index + 1);
        }),
        UPLEFT(UP.strategy.andThen(LEFT.strategy)),
        UPRIGHT(UP.strategy.andThen(RIGHT.strategy)),
        DOWNLEFT(DOWN.strategy.andThen(LEFT.strategy)),
        DOWNRIGHT(DOWN.strategy.andThen(RIGHT.strategy));

        private Function<Block, Block> strategy;

        MovingStrategy(Function<Block, Block> strategy) {
            this.strategy = strategy;
        }

        public Block apply(Block block) {
            return this.strategy.apply(block);
        }
    }

에..  그러니까...  이늄전략이 있는데 Block 이 있으면 그 블록에서 처리를 해서 다시 블록을 반환하는 Function 인터페이스를 가지고 있는 이늄전략인거죠.. 

 

UP 의 중요부분은 index - 가로길이 블록을 가져오는 것
LEFT 는 index -1 의 블록을 가져오는 것

그리고 대각선부분은 andThen 으로 좌우 이동부분과 상하이동부분을 조합해서 사용을 하게 됩니다.

 

블록이 잠시 궁금할 수도 있어서.. 코드는 대략 이런 느낌인..

static class Block {
        private static Block OUTOFGAME = new Block(-1, null);
        private final int index;
        private int count;
        private final Game game;
        private boolean mine;

        public Block(int number, Game game) {
            this.index = number;
            this.game = game;
        }

        public Block getBlock(int index) {
            if (this == Block.OUTOFGAME) return this;
            return this.game.getBlock(index);
        }
}

 

위의 지인개발자의 구현과 조금 다른 점이 있다면 이 이늄전략 코드에서는 널객체 패턴을 사용했다는 것입니다. 

https://johngrib.github.io/wiki/null-object-pattern/

널 오브젝트 패턴 (Null Object Pattern)

지뢰바깥으로 나간 Block 에 대해서는 OUTOFGAME 이라고 정의를 하여

null 처리보다는 조금 더 의미를 부여를 하고자 했습니다만.. 뭐... 

 

그러면 이동전략을 정의했으니 지인에게 말했던 핵심부분인 

1. 랜덤 숫자를 만든다 (코딩도장문제는 지뢰위치가 제공되기 때문에 숫자를 읽어들여서 지뢰숫자를 제공해주면됩니다)

2. 블록객체 만든다

3. 숫자를 지뢰로 만들어서 지뢰 주변의 숫자(블록)들의 카운트를 1씩 늘려준다

라는 부분을 코드로 표현하면

 

public Game(GameOption gameOption) {
  this.width = gameOption.getWidth();
  this.height = gameOption.getHeight();
  int size = width * height;

  // set blocks
  this.blocks = new ArrayList<>(size);
  for (int i = 0; i < size; i++) {
  this.blocks.add(i, new Block(i, this));
  }

  // 밑으로 지뢰매설 코드
}

블록세팅하고 밑에서 지뢰매설

// mines
Set<Integer> mines = gameOption.getMineNums();
mines.stream()
	.map(this::layMine)
	.map(block -> block.getAdjacentBlock(MovingStrategy.values()))
	.flatMap(Collection::stream)
	.filter(Block::isInGameBlock)
	.forEach(Block::plusCount);

숫자를 지뢰로 만들어서 지뢰매설(layMine) 하고 

블록 주변의 인접블록을 얻어서 ( getAdjacentBlock)

아참 OUT OF GAME 블록은 걸르고 ( isInGameBlock ?)

이렇게 나온 블록에 대하여 각각 숫자 +1 씩 카운트 ( plusCount )

 

대략 이런 느낌이 나오게 되는 거겠죠...흠.. 

전체 코드는 코딩도장 아니면 gist 로 보실 수 있겠습니다. 

http://codingdojang.com/scode/421?langby=java#answer-filter-area

https://gist.github.com/arahansa/7834a0a648f8c4ff3dbe2f81cebbd0c3

 

 

뭐 돌리면 문제랑 답변에 맞춰서 이렇게 나오긴합니당..

실행 메인코드 부분이고..

public static void main(String[] args) {
        String input = """
                4 4
                *...
                ....
                .*..
                ....
                """;
        new Game(new GameOption(input)).print();
        input = """
                3 5
                **...
                .....
                .*...
                """;
        new Game(new GameOption(input)).print();

        System.out.println("25 칸 짜리");
        new Game(new GameOption(5, 5, getRandomNumbers(25))).print();

        System.out.println("49 칸 짜리");
        new Game(new GameOption(7, 7, getRandomNumbers(49))).print();

        System.out.println("100 칸 짜리");
        new Game(new GameOption(10, 10, getRandomNumbers(100))).print();
    }

 

입력과 출력대로는 잘 나오는 듯합니다만..음? 

 

5) 좀 더 적어보고 싶던 이야기.. 

5-1) 경계값은 잘 따져봐야.. 

(세상 만사 다 겉멋이겠습니다만..)

모든 유저가 입력하는 숫자값들은 올바른 타입인지, 경계값은 제대로 들어왔는지 검사를 해봐야합니다. 

모든 토이프로젝트의 고민이기도하고 실무에서의 고민이기도하고.. 심지어 유튜브에서도 일어나는 일이기도 하지요.. 

 

강남스타일은 어떻게 유튜브 조회수 측정 서버에 문제를 일으켰나

어떤 경계선부터 우리의 검증이 통과된 값으로 처리할 것인가.. 

[검증] 이라는 단어를 처리하기 위해 어떤 기술들을 사용할 것인가. 하는 고민이 필요한 부분이겠습니다만.. 

 

JSR303, JSR349 라는 스펙쪽이 떠오릅니다만 자세한 설명은 생략합니다. 

 

 

Jakarta Bean Validation - Bean Validation 1.1 (JSR 349)

 

Bean validation 1.1

여기서의 빈.. 자바빈이란? 요 빈..?

 

 

자바빈즈 - 위키백과, 우리 모두의 백과사전

실제 구현코드쪽을 좀 보면 

static class GameOption {
        @Min(2)
        @Max(120)
        int width;
        @Min(2)
        @Max(120)
        int height;
        @NotEmpty
        Set<Integer> mineNums;

        public GameOption(int width, int height, Set<Integer> mine) {
            this.width = width;
            this.height = height;
            this.mineNums = mine;

            ValidationUtil.validateArgs(this);
        }
}

이런식의 javax.validation 어노테이션들을 이용하여 경계값 조건들을 지정하고

요런식으로 한번 만들어보면

public class ValidationUtil {

    static Validator validator = Validation.buildDefaultValidatorFactory().getValidator();

    public static void validateArgs(Object object){
        Set<ConstraintViolation<Object>> validate = validator.validate(object);
        if(validate.iterator().hasNext()){
            ConstraintViolation<Object> next = validate.iterator().next();
            throw new IllegalArgumentException("에러 필드 " + next.getPropertyPath()+ " 은(는) " + next.getMessage());
        }
    }
}

 

다음과 같은 테스트를 진행해볼 수 있겠죠...흠.. 

 

5-2) 절차적 프로그래밍과 객체지향 그리고 유지보수? 

 

5-2-1) 난이도의 변경

저는 객체지향은 캡상추다밖에 모르는 객체지향 늅늅이 이겠습니다만..

절차적 프로그래밍이라는 개념에 대해서 한번 생각을 해볼 수는 있겠습니다.

https://ko.wikipedia.org/wiki/%EC%A0%88%EC%B0%A8%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

절차적 프로그래밍 - 위키백과, 우리 모두의 백과사전

제가 개념원리에 약해서.. 로직과 데이터의 혼재랄까요... 

만약에 위에서 설명한 난이도의 변경에 대해서 생각해보겠습니다.

처음에는 대각선까지만 퍼지는 우측의 모델로 개발이 되었는데 이 지뢰찾기가 흥행해서 어린이용으로도 개발한다고 합니다.

사장님 : 좋아 성공했어 어린이용도 출시 가즈아ㅏㅏ 

개발자 : 네.. 저 로직 만드는데도 어려웠는데 상황별로 ...? 띠용..?

 

절차적으로 생각해본다면.. 

for(int i j=){

  if( mode == "어린이용"){

   샬라샬라

  else ( mode == "성인용" ){

    샬라샬라

}

 

이렇게 적어야할수도 있겠죠... 하지만 윗 방법이라면 

이동전략에 대해서 어린이용, 성인용(?)을 

어린이용 = UP, DOWN, LEFT, RIGHT

성인용 = UP, DOWN, UP, DOWN, LEFT, RIGHT, UPLEFT, (..생략).. 

 

이렇게 필드정의를 하고서 게임옵션에 따라 갈아낄 수도 있을 것같다는 생각입니다. 

 

5-2-2) 또다른 기능 - 인접 0 을 터뜨려라 

또 다른 기능을 생각해볼까요...?

지뢰찾기에서는 0 을 누르면 주변의 인접 0 에 대하여 열어주는 기능이 있습니다. 

 

우리의 욕심쟁이 사장님은 지뢰찾기의 흥행에 고민하여 다음과 같은 요구사항을 주실 것같습니다. 

 

사장님 : 좋아 이 기세를 몰아서, 0이 열려질 때 천지파열무같은 효과를 주는 거야.. 이봐 김개발, 할 수 있겠지? 

 

( 인간의 욕심은 끝이 없고, 세상의 삼라만상은 변화한다...)

0을 터뜨리는것도 모잘라서, 화려한 조명의 효과까지..?

정신이 아득해지는 순간입니다만..

절차적인 부분이라면 (사실 절차적 코드는 별로 생각을 안 해봤습니다만;;)

주변인접으로 계속 터뜨려나가줘야되는 개념일까요? 흠... 

사실 다른 쪽 코드는 신경을 잘 안 써서 모르겠습니다만(^^a;;)

제쪽에서 만약에 인접 0을 터뜨린다면 0을 터진 위치를 기준으로 근접의 0을 찾아 열게하는 전파모델을 생각해볼 것같다는 생각은 드네요.. 만약에 이펙트를 원한다면 이 사이에 이펙트 효과를 끼어서 넣어주면 될지도..

 

 

5-2-3) 또다른 욕심 - 이제는 체스를 만들어주세요..

.. 인간의 욕심은 끝이 없습니다. 

 

이제 개발자는 지뢰찾기를 가지고서 도망을 가고 싶어합니다.

하지만 지뢰찾기로는 성공할 수가 없겠죠.

자신의 체스버전을 만들어야 뭔가 될 것같습니다. 개발자도 욕심이 끝이 없었습니다.

 

개발자 : 후후 . 준비는 되어있어 ...

MovingStrategy 를 이용하면 난 이걸로 체스로 이동하는 모델을 만들수도 있지 않겠지...?

라는 망상을 해보며 그는 오늘도 야근을 합니다...(음?)

 

글쓰다가 이제 힘들어서 급하게 마무리 하겠습니다..

 

아 하나 더 고민할 부분? 

box의 이동방법은.. 

box.up()

box.move(이동전략)

그리고 위에서 기술한 전략.적용(box) 

뭐 이렇게도 여러 고민이 생기는데 힘들어서 이만.. 

 

마치며?

에..  글을 적는 이유는 제가 관종은 아닙니다만..

개발을 하는 사람이라면 응당 자신의 구현코드를 가지고
다른 사람과 이야기를 해보고 싶은 생각이 있는 것 아니겠심니까만은.. 

 

( 음..칭찬이...맞는거였죠? 잠시 코딩 강사를 이야기하다가 ;; )

흠흠?!. 관종의 기질은 아니라고 생각합니다만( -_ -)a 아무튼 

 

(재밌게 보셨다면 코딩도장에 따봉한번 ;ㅅ;  )

 

 

재미있으셨다면 따봉 한번 부탁드리겠습니다만. ㅋㅋ ( 너무 지뢰찾기 해답이 2차원 배열만 있어서 적어보았네요 ) 

 

코딩도장

( 따봉주소는 이 주소인데 직접클릭이 안되는듯..? )

(뭘 지뢰찾기에 거창하게 이렇게 글을 쓰는 것인가 ; )

 

개발이란 뭘까요..

1) 동작하는 코드 구현

2) 경우의 수를 따지는 구현

3) 향후 변경 가능성에 대비한 구현..?

아직도 잘 모르겠습니다.

그냥 뭐 심심할때 고민하면서 좋은코드면 좋은코드대로 나쁜코드면 나쁜 코드대로 즐겁게 하면 되겠죠

 

 

추천 링크

다 마스터하진 못했지만.. 오브젝트와 코드스피츠 오브젝트 강의는 참 좋습니다.  좋은 책과 강의 감사합니다.

 

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791158391409&orderClick=LEa&Kc=

오브젝트 - 교보문고

https://www.youtube.com/watch?v=sWyZUzQW3IM&list=PLBNdLLaRx_rI-UsVIGeWX_iv-e8cxpLxS

 

아.. 오늘 날씨는 더운게 지뢰찾기 하기 참 좋은 날씨같습니다. . 그럼 이만. 

 

 

======

세상에 나쁜 코드는 없다.

친절히 코드로 이야기하려합니다 by 아라한사