[프로그래머스][LV.1] [PCCE 기출문제] 9번 / 이웃한 칸 | python3

문제링크:  [PCCE 기출문제] 9번 / 이웃한 칸

---

문제설명

각 칸마다 색이 칠해진 2차원 격자 보드판이 있습니다. 그중 한 칸을 골랐을 때, 위, 아래, 왼쪽, 오른쪽 칸 중 같은 색깔로 칠해진 칸의 개수를 구하려고 합니다.

보드의 각 칸에 칠해진 색깔 이름이 담긴 이차원 문자열 리스트 board와 고른 칸의 위치를 나타내는 두 정수 h, w가 주어질 때 board[h][w]와 이웃한 칸들 중 같은 색으로 칠해져 있는 칸의 개수를 return 하도록 solution 함수를 완성해 주세요.

이웃한 칸들 중 몇 개의 칸이 같은 색으로 색칠되어 있는지 확인하는 과정은 다음과 같습니다.

1. 정수를 저장할 변수 n을 만들고 board의 길이를 저장합니다.
2. 같은 색으로 색칠된 칸의 개수를 저장할 변수 count를 만들고 0을 저장합니다.
3. h와 w의 변화량을 저장할 정수 리스트 dh, dw를 만들고 각각 [0, 1, -1, 0], [1, 0, 0, -1]을 저장합니다.
4. 반복문을 이용해 i 값을 0부터 3까지 1 씩 증가시키며 아래 작업을 반복합니다.
    4-1. 체크할 칸의 h, w 좌표를 나타내는 변수 h_check, w_check를 만들고 각각 h + dh[i], w + dw[i]를 저장합니다.
    4-2. h_check가 0 이상 n 미만이고 w_check가 0 이상 n 미만이라면 다음을 수행합니다.
        4-2-a. board[h][w]와 board[h_check][w_check]의 값이 동일하다면 count의 값을 1 증가시킵니다.
5. count의 값을 return합니다.

위의 의사코드와 작동방식이 다른 코드를 작성해도 상관없습니다.

 

제한조건

- 1 ≤ board의 길이 ≤ 7
    - board의 길이와 board[n]의 길이는 동일합니다.
- 0 ≤ h, w < board의 길이
- 1 ≤ board[h][w]의 길이 ≤ 10
    - board[h][w]는 영어 소문자로만 이루어져 있습니다.

---

 

문제풀이

하라는 대로 하니까 간단하게 풀림.

 

나의코드

def solution(board, h, w):
    count = 0
    n=len(board)
    dh=[0,1,-1,0]
    dw=[1,0,0,-1]
    
    for i in range(4):
        h_check=h+dh[i]
        w_check=w+dw[i]
        if 0 <= h_check < n and 0 <= w_check < n:
            if board[h][w] == board[h_check][w_check]:
                count+=1
    return count

 

---

 

참고하기

def solution(board, h, w):
    answer = 0

    if 0 < h:
        if board[h][w] == board[h-1][w]: answer += 1
    if 0 < w:
        if board[h][w] == board[h][w-1]: answer += 1
    if h < len(board) - 1:
        if board[h][w] == board[h+1][w]: answer += 1
    if w < len(board[0]) - 1:
        if board[h][w] == board[h][w+1]: answer += 1

    return answer

이 코드가 왜 되는지 이해가 안됨.

 

---

코드 분석

def solution(board, h, w):
    answer = 0  # 같은 값의 개수를 저장할 변수

    # 위쪽 확인
    if 0 < h:  # h가 0보다 크면(즉, 첫 번째 행이 아니면)
        if board[h][w] == board[h-1][w]:  # 위쪽 값과 비교
            answer += 1  # 같으면 +1 증가

    # 왼쪽 확인
    if 0 < w:  # w가 0보다 크면(즉, 첫 번째 열이 아니면)
        if board[h][w] == board[h][w-1]:  # 왼쪽 값과 비교
            answer += 1  # 같으면 +1 증가

    # 아래쪽 확인
    if h < len(board) - 1:  # h가 마지막 행보다 작으면(즉, 마지막 행이 아니면)
        if board[h][w] == board[h+1][w]:  # 아래쪽 값과 비교
            answer += 1  # 같으면 +1 증가

    # 오른쪽 확인
    if w < len(board[0]) - 1:  # w가 마지막 열보다 작으면(즉, 마지막 열이 아니면)
        if board[h][w] == board[h][w+1]:  # 오른쪽 값과 비교
            answer += 1  # 같으면 +1 증가

    return answer  # 상하좌우 중 같은 값의 개수를 반환

---

왜 되는 걸까?

• (h, w) 좌표에서 상하좌우에 있는 값과 현재 위치의 값을 비교하는데, 인덱스 범위를 초과하지 않도록 if 조건을 사용해서 안전하게 검사하고 있음.
• 예를 들어, (h, w)가 (1, 1)이고 아래 board가 주어진 경우를 생각해보자.

board = [
    [1, 2, 3],
    [4, 1, 2],
    [1, 2, 1]
]

여기서 h=1, w=1이면 board[1][1] = 1이고, 상하좌우를 비교하면:

• 위쪽(board[0][1] = 2) → 다름
• 왼쪽(board[1][0] = 4) → 다름
• 아래쪽(board[2][1] = 2) → 다름
• 오른쪽(board[1][2] = 2) → 다름

즉, 같은 값이 없으므로 answer = 0을 반환.

---

예제 실행

board = [
    [1, 1, 2],
    [2, 1, 2],
    [1, 2, 1]
]
print(solution(board, 1, 1))  # h=1, w=1 위치에서 실행

이 경우 board[1][1] = 1이고,

• 위쪽(board[0][1] = 1) → 같음 (+1)
• 왼쪽(board[1][0] = 2) → 다름
• 아래쪽(board[2][1] = 2) → 다름
• 오른쪽(board[1][2] = 2) → 다름

그러므로 1이 반환됨.

---

정리

✅ 인덱스 범위를 벗어나지 않도록 조건문(if)을 먼저 확인
✅ 현재 위치와 상하좌우의 값을 비교하여 같은 개수를 센다
✅ 시간 복잡도는 O(1)로 매우 빠름 (항상 4번 이하의 비교만 수행)

 

---

Q. 어느 코드가 시간복잡도가 더 빠를까?

 

두 코드 모두 시간 복잡도는 O(1)(상수 시간)로 동일하지만, 두 번째 코드가 조금 더 효율적이야. 이유를 분석해볼게.

---

비교 분석

1️⃣ 첫 번째 코드

def solution(board, h, w):
    answer = 0

    if 0 < h:
        if board[h][w] == board[h-1][w]: answer += 1
    if 0 < w:
        if board[h][w] == board[h][w-1]: answer += 1
    if h < len(board) - 1:
        if board[h][w] == board[h+1][w]: answer += 1
    if w < len(board[0]) - 1:
        if board[h][w] == board[h][w+1]: answer += 1

    return answer

• 최대 4번의 조건문 검사를 수행
  → if 문을 하나씩 따로 체크하여 범위를 벗어나지 않는지 검사함.
• 각 방향별로 별도 조건문을 사용
  → 명확하지만, 반복적인 코드가 많음.

---

2️⃣ 두 번째 코드

def solution(board, h, w):
    count = 0
    n = len(board)  # 보드의 크기
    dh = [0, 1, -1, 0]  # x축(행) 이동 방향
    dw = [1, 0, 0, -1]  # y축(열) 이동 방향

    for i in range(4):  # 4방향 탐색
        h_check = h + dh[i]
        w_check = w + dw[i]
        if 0 <= h_check < n and 0 <= w_check < n:  # 범위 체크
            if board[h][w] == board[h_check][w_check]:  # 값 비교
                count += 1
    return count

• 리스트를 사용하여 방향을 한 번에 처리
  → 중복된 if 문을 줄이고, 반복문(for)을 이용해 4방향을 처리함.
• 한 줄로 범위 검사
  → if 0 <= h_check < n and 0 <= w_check < n: 로 범위를 빠르게 체크 가능.
• 반복문을 사용해 코드 가독성이 좋음
  → 코드 길이가 짧고 유지보수가 쉬움.

---

시간 복잡도 비교

코드 시간 복잡도 이유

첫 번째 코드	O(1)	4번의 조건문을 각각 실행
두 번째 코드	O(1)	4번의 반복문을 실행 (하지만 코드가 더 간결)

🔹 결론:
👉 둘 다 O(1)으로 속도 차이는 거의 없음, 하지만 두 번째 코드가 가독성과 유지보수 측면에서 더 좋음.
👉 특히, 4방향 이상(예: 8방향)으로 확장할 경우, 두 번째 코드가 더 유리함.