Sign in Subscribe
PS

[PS] BOJ 4396 / 지뢰찾기

Minjun Kim

• 4 min read
[PS] BOJ 4396 / 지뢰찾기
문제 링크: https://www.acmicpc.net/problem/4396
Thumbnail: Photo by MW (Unsplash)

​항상 썸네일 이미지를 Unsplash에서 찾고 있는데, 도저히 지뢰 찾기 이미지를 찾을 수 없어서 그냥 게임 맵처럼 보이는 걸로 들고 왔습니다.. 😅

풀이

지뢰 위치 기록하기

먼저, \(N \times N\)의 크기로 지뢰의 위치가 주어집니다. 지뢰의 위치를 좌표꼴로 저장해도 되지만, 다음에 입력 받을 "열려 있는" 타일의 지도를 고려해 그냥 \(N \times N\)크기의 배열에 지뢰가 있는 위치는 True, 아니면 False로 기록하기로 했습니다.

bombs = [[False for _ in range(N)] for _ in range(N)]
# 폭탄 좌표 처리
for y in range(N):
    line = input().strip()
    for x in range(N):
        if line[x] == "*":
            bombs[y][x] = True

지뢰 위치 입력받기

주변의 폭탄 개수 세기

​이제 열려 있는 각 타일에 대해 주변에 있는 지뢰의 개수를 세어주는 함수를 만들어 봅시다. 현재 타일 주변의 \(3 \times 3\)의 범위 안에 있는 지뢰의 개수를 세어 정수 값으로 반환해주면 됩니다.

def count_bombs(x, y):
    """자기 주위의 3x3 범위 안에 포함된 폭탄의 개수를 센다. (N이 10 이하이므로 매번 반복하면서 찾아도 시간 안에 풀 수 있다.)"""
    result = 0
    for dy in (-1, 0, 1):
        for dx in (-1, 0, 1):
            if 0 <= x + dx < N and 0 <= y + dy < N and bombs[y + dy][x + dx]:
                result += 1
    return result

주변에 있는 지뢰 개수 세기

열려 있는 타일 채우기

열려 있는 타일의 지도를 한 줄씩 입력 받아서, 'x'가 있는 칸은 주변의 지뢰 개수로 바꿔줍니다.

# 칠해야 하는 범위 입력받기
board = []
failed = False
for y in range(N):
    line = list(input().strip())
    for x in range(N):
        if line[x] == "x":
            line[x] = count_bombs(x, y)
    board.append(line)

열려 있는 타일의 지도를 입력 받아, 'x'가 있는 칸은 주변의 지뢰 개수로 바꿔준다.

이때, 문제의 출력 조건을 자세히 보면 다음과 같은 내용이 있습니다:

지뢰가 있는 칸이 열렸다면 지뢰가 있는 모든 칸이 별표(*)로 표시되어야 한다.

즉, 열린 타일 중에 지뢰가 있는 칸이 있다면, 지뢰가 있던 위치는 다시 '*'로 바꿔주어야 합니다. 따라서 위 반복문을 조금 수정해줍시다

# 칠해야 하는 범위 입력받기
board = []
failed = False
for y in range(N):
    line = list(input().strip())
    for x in range(N):
        if line[x] == "x":
            if bombs[y][x]:
                failed = True
            else:
                line[x] = count_bombs(x, y)
    board.append(line)

지뢰가 있는 칸이 열렸는지 검사

이후 failed가 True라면, 모든 지뢰의 위치를 '*'로 바꿔줍니다.

if failed:  # 만약 폭탄이 있는 위치가 열렸다면, 모든 폭탄이 *로 표시되어야 한다.
    for y in range(N):
        for x in range(N):
            if bombs[y][x]:
                board[y][x] = "*"

전체 코드

input = open(0).readline
N = int(input().strip())
bombs = [[False for _ in range(N)] for _ in range(N)]
# 폭탄 좌표 처리
for y in range(N):
    line = input().strip()
    for x in range(N):
        if line[x] == "*":
            bombs[y][x] = True

def count_bombs(x, y):
    """자기 주위의 3x3 범위 안에 포함된 폭탄의 개수를 센다. (N이 10 이하이므로 매번 반복하면서 찾아도 시간 안에 풀 수 있다.)"""
    result = 0
    for dy in (-1, 0, 1):
        for dx in (-1, 0, 1):
            if 0 <= x + dx < N and 0 <= y + dy < N and bombs[y + dy][x + dx]:
                result += 1
    return result

# 칠해야 하는 범위 입력받기
board = []
failed = False
for y in range(N):
    line = list(input().strip())
    for x in range(N):
        if line[x] == "x":
            if bombs[y][x]:
                failed = True
            else:
                line[x] = count_bombs(x, y)
    board.append(line)

if failed:  # 만약 폭탄이 있는 위치가 열렸다면, 모든 폭탄이 *로 표시되어야 한다.
    for y in range(N):
        for x in range(N):
            if bombs[y][x]:
                board[y][x] = "*"

print("\n".join(map(lambda line: "".join(map(lambda c: str(c), line)), board)))

solution.py