[Code Tree][Python] IL Simulation 1차원 바람

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨:  IL / Simulation / 격자 안에서 밀고 당기 / 연습 문제
• 문제 유형: Simulation
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

Trail 4 / Chapter 1 / Lesson 2 / 연습 문제

https://www.codetree.ai/trails/complete/curated-cards/challenge-The-1D-wind-blows/description

Code Tree | Learning to Code with Confidence

 

 

[코드]

1. 문제 이해 및 분석

- 입력: 배열의 크기, 바람이 부는 횟수, 바람 배열(행, 방향) 

- 출력: 바람으로 인한 이동이 완료된 배열

 

[문제 설명]

바람이 부는 행과 방향이 주어진다. 

• 'L' : 왼쪽에서 오른쪽으로 불며, 오른쪽으로 배열을 한 칸씩 민다. 
• 'R': 오른쪽에서 왼쪽으로 불며, 왼쪽으로 배열을 한 칸씩 민다. 

 

밀고 난 후의 행과 그 행의 위아래 행, 열의 값이 같으면 밀린 행의 바람 방향과 반대로 배열을 민다. 

만약 값이 일치하지 않는다면 밀지 않는다. 

배열 전체를 확인한다. 

 

2. 알고리즘 설계

- 필요한 함수들 구상

• main(): 입출력 
• solution(): 입력을 받아 move를 수행하고 출력을 반환해줄 함수
• move(): 왼쪽, 오른쪽으로 배열 밀기
• chk(): 밀린 행의 위아래 해오가 열의 숫자가 일치하는지 확인

---

1. main() - 입출력을 구현해준다. 

def main():
    n, m, q = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    winds = [(int(r), d) for r, d in [input().split() for _ in range(q)]]
    
    for rowIdx, dr in winds:
        a = solution(m, a, rowIdx, dr)

    for row in a:
        print(*row)


if __name__ == "__main__":
    import sys, io

    sys.stdin = io.StringIO(
        """3 3 2
1 2 3
3 2 1
3 3 3
3 L
1 L"""
    )
    # 예제 출력
    # 3 1 2
    # 2 1 3
    # 3 3 3 

    main()

 

 

2. move() - 배열을 방향에 맞춰 밀기

좌우로 배열을 한 칸씩 미는 건, tmp 변수를 만들어주고, 값을 임시 저장 했다가 다시 추가해준다.

왼쪽으로 미는 경우와 오른쪽으로 미는 경우를 나누어주었다.  

이 부분은 구현이 어렵지 않다. 

def move(m, a, rowIdx, dr) -> list[int]:
    # 왼쪽으로 밀기 
    if dr == 'L':
        tmp = a[rowIdx-1][m-1]
        for i in range(m-1, 0, -1):
            a[rowIdx-1][i] = a[rowIdx-1][i-1]
        a[rowIdx-1][0] = tmp

    # 오른쪽으로 밀기 
    else:
        tmp = a[rowIdx-1][0]
        for i in range(1, m):
            a[rowIdx-1][i-1] = a[rowIdx-1][i]
        a[rowIdx-1][m-1] = tmp

    return a

 

 

 

3. chk() - 밀린 행 위아래 행과 열의 숫자와 일치하는지 확인

이 부분에서 무한 루프가 발생했었다. 

바람이 불면 전체적으로 전파가 되는지 확인을 해야 하는데, 방문 체크를 하지 않아서 무한 루프가 발생했다. 

next_row, next_dir을 설정해, 방문하면 visited에 추가해주고

검사할 때 visited에 없으면 이동해야 하는 moves 배열에 추가해주었다. 

위쪽과 아래쪽의 경우를 나누었는데, 방향이 달라서 하나씩 진행해야 겠다고 생각해서다. 

def chk(m, a, rowIdx, dr, visited) -> list[tuple[int, str]]:
    # 밀린 행 위아래 행과 열의 숫자와 일치하는지 확인
    moves = []

    row = rowIdx - 1

    # 첫 번째 행이 아닌 경우 위쪽 검사
    if 0 < row:
        next_row = row  # 현재 행 위의 행이 이동할 차례 
        next_dir = 'R' if dr == 'L' else 'L'
        
        if (next_row, next_dir) not in visited:
            for i in range(m):
                if a[row][i] == a[row-1][i]:
                    moves.append((next_row, next_dir))
                    break

    # 마지막 행이 아닌 경우 아래쪽 검사                      
    if row < len(a)-1:
        next_row = row + 2  # 1-based index로 변환
        next_dir = 'R' if dr == 'L' else 'L'

        if (next_row, next_dir) not in visited:
            for i in range(m):
                if a[row+1][i] == a[row][i]:
                    moves.append((next_row, next_dir))
                    break
    
    return moves

 

 

4. solutions() - 이동, visited, 전파될 행 체크 

함수를 호출할 사실상 main 함수이다. 

처음 구현할 때 생각하는대로 구조가 설계되었는지 확인하기 위해 밀린 행의 바로 위아래 행만 확인했는데,

문제에서는 전체 행을 확인해야해서 헤맸었다. 

 

먼저 기준이 되는 행을 밀고, visited 방문 체크에 추가해준 후 chk()를 실행해 이동 가능한 지 확인해주었다. 

전체 행을 확인하고 이동해야 하기 때문에 while을 사용해주었다. 

 

반복하면서 visited에 들어있으면 continue, 없으면 move 후 visited 배열에 추가 

def solution(m, a, rowIdx, dr) -> list[int]:
    visited = set()

    # 첫 번째 이동
    a = move(m, a, rowIdx, dr)
    visited.add((rowIdx, dr))  # 첫 이동 기록

    # 전파 이동 체크 및 실행
    moves = chk(m, a, rowIdx, dr, visited)
    while moves:
        new_moves = []
        for curr_row, curr_dir in moves:
            if (curr_row, curr_dir) in visited:
                continue

            a = move(m, a, curr_row, curr_dir)
            visited.add((curr_row, curr_dir))  # 이동 기록

            # 이동 후 추가 전파 이동 체크
            add_moves = chk(m, a, curr_row, curr_dir, visited)
            new_moves.extend(add_moves)
        moves = new_moves

    return a

 

 

set을 사용해준 이유는 검색 효율성, 중복 방지, 메모리 효율성

new_moves.extend(add_moves) 한 이유는, (curr_row, curr_dir) 을 append 하면 리스트로 추가되기 때문이다. 

# append 예시
moves = []
moves.append((2, 'L'))  # moves = [(2, 'L')]

# extend 예시
new_moves = []
add_moves = [(2, 'L'), (3, 'R')]
new_moves.extend(add_moves)  # new_moves = [(2, 'L'), (3, 'R')]

# 만약 여기서 append를 썼다면:
new_moves.append(add_moves)  # new_moves = [[(2, 'L'), (3, 'R')]]  # 리스트 안에 리스트가 들어감

---

[최종 코드]

def chk(m, a, rowIdx, dr, visited) -> list[tuple[int, str]]:
    # 밀린 행 위아래 행과 열의 숫자와 일치하는지 확인
    moves = []

    row = rowIdx - 1

    # 첫 번째 행이 아닌 경우 위쪽 검사
    if 0 < row:
        next_row = row  # 현재 행 위의 행이 이동할 차례 
        next_dir = 'R' if dr == 'L' else 'L'
        
        if (next_row, next_dir) not in visited:
            for i in range(m):
                if a[row][i] == a[row-1][i]:
                    moves.append((next_row, next_dir))
                    break

    # 마지막 행이 아닌 경우 아래쪽 검사                      
    if row < len(a)-1:
        next_row = row + 2  # 1-based index로 변환
        next_dir = 'R' if dr == 'L' else 'L'

        if (next_row, next_dir) not in visited:
            for i in range(m):
                if a[row+1][i] == a[row][i]:
                    moves.append((next_row, next_dir))
                    break
    
    return moves


def move(m, a, rowIdx, dr) -> list[int]:
    # 왼쪽으로 밀기 
    if dr == 'L':
        tmp = a[rowIdx-1][m-1]
        for i in range(m-1, 0, -1):
            a[rowIdx-1][i] = a[rowIdx-1][i-1]
        a[rowIdx-1][0] = tmp

    # 오른쪽으로 밀기 
    else:
        tmp = a[rowIdx-1][0]
        for i in range(1, m):
            a[rowIdx-1][i-1] = a[rowIdx-1][i]
        a[rowIdx-1][m-1] = tmp

    return a


def solution(m, a, rowIdx, dr) -> list[int]:
    visited = set()

    # 첫 번째 이동
    a = move(m, a, rowIdx, dr)
    visited.add((rowIdx, dr))  # 첫 이동 기록

    # 전파 이동 체크 및 실행
    moves = chk(m, a, rowIdx, dr, visited)
    while moves:
        new_moves = []
        for curr_row, curr_dir in moves:
            if (curr_row, curr_dir) in visited:
                continue

            a = move(m, a, curr_row, curr_dir)
            visited.add((curr_row, curr_dir))  # 이동 기록

            # 이동 후 추가 전파 이동 체크
            add_moves = chk(m, a, curr_row, curr_dir, visited)
            new_moves.extend(add_moves)
        moves = new_moves

    return a


def main():
    n, m, q = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    winds = [(int(r), d) for r, d in [input().split() for _ in range(q)]]
    
    for rowIdx, dr in winds:
        a = solution(m, a, rowIdx, dr)

    for row in a:
        print(*row)


if __name__ == "__main__":
    import sys, io

    sys.stdin = io.StringIO(
        """3 3 2
1 2 3
3 2 1
3 3 3
3 L
1 L"""
    )
    # 예제 출력
    # 3 1 2
    # 2 1 3
    # 3 3 3 

    main()