[SW Expert Academy, SWEA 14413] 격자판 칠하기 (python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AYEXgKnKKg0DFARx&categoryId=AYEXgKnKKg0DFARx&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

---

※ SW expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

728x90

---

내 생각

처음엔 다음과 같이 풀었다.

배열을 (0, 0)부터 (n - 1, m - 1)까지 훑으며 (i, j)일 때 (i, j + 1)나 (i + 1, j)가 (i, j)와 같은 문자('#'일 땐 '#', '.'일 땐 '.')이면 impossible 출력하고 다른 문자('#'일 때 '.', '.'일 때 '#')라면 넘어가고 '?'일 경우엔 다른 문자로 바꿔준다.

중간에 impossible로 바뀌지 않고 반복문을 끝까지 마치면 possible이 출력되게 코드를 짰다.

# 테스트 케이스의 수 t 입력
t = int(input())

for test_case in range(1, t + 1):
	# 행의 수 n, 열의 수 m 입력
	n, m = map(int, input().split())
	# 2차원 배열의 동, 남 이동
	dx = [0, 1]
	dy = [1, 0]

	# 문자열 입력
	array = []
	for i in range(n):
		array.append(list(input()))

	result = ''
	for i in range(n):
		for j in range(m):
			# 동쪽, 남쪽 중 하나라도 같은 문자라면 답은 imposiible
			# 모두 다른 문자라면 continue
			# ?라면 #일 경우 .을, .일 경우 #를 찍어준다.
			for k in range(2):
				# 인덱스 범위 체크
				if i + dx[k] < n and j + dy[k] < m:
					if array[i + dx[k]][j + dy[k]] == '?':
						if array[i][j] == '#':
							array[i + dx[k]][j + dy[k]] = '.'
						elif array[i][j] == '.':
							array[i + dx[k]][j + dy[k]] = '#'
					elif array[i][j] == array[i + dx[k]][j + dy[k]]:
						result = "impossible"
						break
			# 답이 이미 impossible이면 반복문 빠져 나오게 하기
			if result == "impossible":
				break
		# 답이 이미 impossible이면 반복문 빠져 나오게 하기
		if result == "impossible":
			break

	if result != 'impossible':
		result = 'possible'

	print("#{} {}".format(test_case, result))

 

이 문제의 댓글을 보고 어떤 행 + 열 인덱스의 합의 값이 짝수일 때 '#'라면 possible일 때는 모든 '#'의 행 + 열 인덱스의 합이 짝수라는 것을 알아내었다.

 

그래서 다음과 같은 순서로 진행되도록 코드를 짰다.

1. 가장 처음으로 '?'가 아닌 문자를 찾는다.

2. 그 문자의 인덱스가 [i][j]라고 할 때, i + j가 짝인지 홀인지 검사한다.

3. 짝이라면 i + j 가 짝인 인덱스에는 모두 그 문자가 와야한다. 홀이라면 마찬가지로 i + j가 홀인 인덱스에는 모두 그 문자가 와야한다.

4. 이때 '?'인 자리는 아무거나 올 수 있으니 신경쓰지 않아도 된다.

# 테스트 케이스의 수 t 입력
t = int(input())

for test_case in range(1, t + 1):
    # 행의 수 n, 열의 수 m 입력
    n, m = map(int, input().split())

	# 문자열 입력
    array = []
    for _ in range(n):
        array.append(list(input()))

    # array[i][j]일 때 i + j가 짝수일 때의 문자와 홀수일 때의 문자
    for i in range(n * m):
        if array[i // m][i % m] == '#':
            if ((i // m) + (i % m)) % 2 == 0:
                even = '#'
                odd = '.'
            else:
                even = '.'
                odd = '#'
            break
        elif array[i // m][i % m] == '.':
            if ((i // m) + (i % m)) % 2 == 0:
                even = '.'
                odd = '#'
            else:
                even = '#'
                odd = '.'
            break

    # array[i][j]일 때, i + j가 홀수일 때는 odd, 짝수일 때는 even과 문자열이 같아야 한다.
    result = ''
    for i in range(n * m):
        # 짝수일 때
        if ((i // m) + (i % m)) % 2 == 0:
            # odd와 문자열이 같다면 실패
            if array[i // m][i % m] == odd:
                result = "impossible"
                break
        # 홀수일 때
        else:
            # even과 문자열이 같다면 실패
            if array[i // m][i % m] == even:
                result = "impossible"
                break

    # 반복문이 끝날 때까지 result가  impossible이 아니라면 result는 possible
    if result != "impossible":
        result = "possible"

    print("#{} {}".format(test_case, result))