Awesome

http://boj.kr/14891 

한 번 명령이 주어질 때 톱니바퀴들이 연쇄적으로 어떻게 회전할지에 대해 생각해보고 그대로 만들면 된다.

톱니바퀴들을 collections의 deque로 저장해서 반시계방향 회전, 시계방향 회전을 쉽게 만들었다. (rotate)

반시계, 시계 방향이 잘 와닿지 않아서 왼쪽, 오른쪽 방향 회전이라고 대충 이름붙였다.

방법은 두 가지가 있다. 하나는 반복문, 하나는 재귀.

코드는 재귀가 더 깔끔해보이지만 실행시간은 완전히 똑같았다.

재귀에 익숙해지지 않는다면 좀 처음부터 와닿긴 힘들고, 반복문이 더 이해하기 쉬운 듯 하다.

# 반복문

각 톱니바퀴의 회전 여부(-1, 0, 1)를 담을 move 리스트를 만들고,

모든 톱니바퀴들의 회전 여부를 검사하고 난 후에 move 대로 회전한다.

import sys
from collections import deque


def calc():
    ret = 0
    for i in range(4):
        if wheel[i][0] == '1':
            ret += 1 * pow(2, i)
    return ret


def start(num, direction):
    move = [0] * 4  # 톱니바퀴들의 회전 여부를 담을 move 리스트
    move[num] = direction  # 일단 주어진 톱니바퀴는 무조건 회전

    # 왼쪽 톱니바퀴들이 회전하는지?
    next_num, next_di = num, direction  # 원본 보존을 위해 next 변수 사용 (오른쪽 톱니바퀴들도 봐야 하기 때문에)
    while 0 <= next_num-1:  # next_num-1 이 회전하는지 안하는지를 볼 것임
        if wheel[next_num][6] != wheel[next_num-1][2]:
            next_di = -next_di
            move[next_num-1] = next_di
            next_num -= 1
        else:  # 움직이지 않으면 바로 빠져나온다
            break

    # 오른쪽 톱니바퀴들이 회전하는지?
    next_num, next_di = num, direction
    while next_num+1 < 4:
        if wheel[next_num][2] != wheel[next_num+1][6]:
            next_di = -next_di
            move[next_num+1] = next_di
            next_num += 1
        else:
            break

    # move 리스트에 작성한 대로 실제로 톱니바퀴를 돌림
    for n, direction in enumerate(move):
        if direction != 0:
            wheel[n].rotate(direction)


if __name__ == '__main__':
    input = sys.stdin.readline
    wheel = [deque(input()[:-1]) for _ in range(4)]
    K = int(input())
    order = [list(map(int, input().split())) for _ in range(K)]

    for num, direction in order:
        start(num-1, direction)
    print(calc())

# 재귀

톱니바퀴 번호 n과 방향 di을 매개변수로 넣어 매번 move_left 함수를 호출하고

함수 내에서는 n이 아닌 n-1 이 회전하는지 확인한다. (if wheel[n][6] != wheel[n-1][2])

회전할 수 있다면 n-1 을 매개변수로 다시 move_left 함수를 호출한다.

재귀에서 돌아올 때 rotate를 실행한다. (위에서 말했듯이 n이 아닌 n-1이 회전하는지 확인했으므로, n-1을 회전시킨다)

n이 아닌 n-1 부터 회전시켰으므로 마지막으로 n을 회전시키고 프로그램을 종료한다.

(n-1 -> n+1, move_left -> move_right 동일)

import sys
from collections import deque


def calc():
    ret = 0
    for i in range(4):
        if wheel[i][0] == '1':
            ret += 1 * pow(2, i)
    return ret


def move_left(n, di):
    if n < 1:
        return
    if wheel[n][6] != wheel[n-1][2]:
        move_left(n-1, -di)
        wheel[n-1].rotate(di)


def move_right(n, di):
    if 2 < n:
        return
    if wheel[n][2] != wheel[n+1][6]:
        move_right(n+1, -di)
        wheel[n+1].rotate(di)


def start(num, direction):
    move_left(num-1, -direction)
    move_right(num-1, -direction)
    wheel[num-1].rotate(direction)


if __name__ == '__main__':
    input = sys.stdin.readline
    wheel = [deque(input()[:-1]) for _ in range(4)]
    K = int(input())  # K번의 명령어
    order = [list(map(int, input().split())) for _ in range(K)]

    for num, direction in order:
        start(num, direction)

    print(calc())

http://boj.kr/14503 

정말 꼼꼼하게 문제 조건을 살펴야 하는구나...라고 느낀 문제.

그리고 코딩 전 직접 시뮬레이션을 해보는 것이 중요하다.

import sys
from copy import deepcopy


def get_back_direction(direct):
    if direct < 2:
        return direct + 2
    else:
        return direct - 2


def get_left_direction(direct):
    if direct == 0:
        return 3
    else:
        return direct - 1


def start(row, col, di):
    visited = deepcopy(board)
    visited[row][col] = 1
    clean_area = 1  # 청소한 영역
    turn_times = 0   # 4방향을 봤는지 카운트해줌
    next_di = di  # 다음 방향

    while True:
        while turn_times < 4: 
            next_di = get_left_direction(next_di)  # 왼쪽으로 한번 돌려봐라
            turn_times += 1
            if visited[row+x[next_di]][col+y[next_di]] == 0:  # 갈 수 있으면 가고
                di = next_di
                row += x[di]
                col += y[di]
                visited[row][col] = 1
                clean_area += 1
                turn_times = 0

            # 왼쪽으로 돌렸는데 갈 수 없으면 실제로 방향을 변경하는 것은 아니고
            # while로 돌아가 다시 왼쪽으로 돌려보는 것

        back_di = get_back_direction(di)  # 4방향 모두 봤는데 갈 수 없으면 후진 시도

        # 후진할 수 있으면(=벽이 아니면) 방향은 유지하고 한칸 빽->while로 돌아가서 거기서 다시 왼쪽으로 돌려보기 시작
        if board[row+x[back_di]][col+y[back_di]] != 1:
            row += x[back_di]
            col += y[back_di]
            turn_times = 0

        # 프로그램 종료
        else:
            break

    return clean_area


if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    r, c, d = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    x = [-1, 0, 1, 0]
    y = [0, 1, 0, -1]
    print(start(r, c, d))

왼쪽으로 돌려볼 때 next_di 를 사용하는 이유.

di를 왼쪽으로 돌릴 때마다 바로바로 업데이트하면 4방향 모두 봤는데 막혀있을 때,

후진 전에다시 원래 방향으로 돌아와야 하기 때문이다. 

board와 로봇 청소기가 사용한 visited는 따로 사용했다. 

로봇청소기가 후진하려고 할 때 벽일 때는 바로 프로그램이 종료되어야 하지만 

청소한 영역(visited = 1)일 때는 후진 가능하기 때문이다...

다시 생각해보니 청소 영역을 2로 체크해도 됐었을 듯.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&

코드는 

https://github.com/ChangmoKang/problem_solving/blob/master/SWEA/2383.py#L74

이 분 코드를 참고했음.

1. 사람이 계단을 선택한다고 생각하지말고, 사람은 여러 명, 계단은 항상 2개이므로 계단이 사람을 선택한다고 생각한다. -> DFS가 됨

2. 계단이라고 해서 큐처럼 진짜 한 칸씩 땡겨오려고 하지 말고, 0이 되면 그 자리에 대기자를 넣는다고 생각을 하자. 

3. 사람들을 어떻게 구별하나 고민하지 말고, 여기서 필요한 정보는 각 사람~계단까지의 거리 뿐임을 기억하자. 중복되도 상관없다. 리스트에 거리만 계산해서 넣으면 끝이다. 

4. 괜히 괜히 괜히 엄청나게 복잡하고 어려운 것 같으면 뭔가 이상하다는 뜻이다. 더 쉬울만한 다른 방법을 생각해보자.

import sys


def init():
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                people.append([i, j])
            elif board[i][j] != 0:  # 1도 아니고 0도 아니면 계단
                stair.append([i, j, board[i][j]])


def calc_distance(pdx, sdx):
    return abs(people[pdx][0] - stair[sdx][0]) + \
            abs(people[pdx][1] - stair[sdx][1])


def start(count, choice):
    global min_time
    if count == people_num:
        wait = [[], []]
        on_stair = [[0, 0, 0], [0, 0, 0]]

        for pdx in range(people_num):  # pdx = people index
            wait[choice[pdx]].append(calc_distance(pdx, choice[pdx]))  # 거리를 대기자 리스트에 넣는다

        wait[0].sort()
        wait[1].sort()

        # 계단1,2 합쳐서 가장 먼저 도착하는 사람을 시작 시간(t)으로 놓는다.
        if wait[0] and wait[1]:
            t = min(wait[0][0], wait[1][0])
        elif wait[0] and not wait[1]:
            t = wait[0][0]
        else:
            t = wait[1][0]

        while wait[0] or wait[1]:  # 대기자가 있을 때까지 반복
            for sdx in range(2):  # sdx = stair index
                for floor in range(3):  # 매번 각 계단의 *세 자리*를 살펴서 
                    if on_stair[sdx][floor] > 0:  # 계단에 누가 있으면
                        on_stair[sdx][floor] -= 1  # 한 층 내려오게 하고
                    if on_stair[sdx][floor] == 0:  # 0이 되면 (=빈 자리가 생김)
                        if wait[sdx] and wait[sdx][0] < t:  # 해당 계단에 대기자가 있고 & 도착할 시간이 지났으면
                            on_stair[sdx][floor] = stair[sdx][H]  # 해당 계단의 높이를 리스트에 넣는다
                            wait[sdx].pop(0)
            t += 1

        t += max(max(on_stair[0]), max(on_stair[1])) - 1
        min_time = min(t, min_time)
        return
    
    else:  # DFS로 순열 찾기 (count == 사람숫자 될 때마다 본격적인 시뮬레이션 시작)
        for i in range(2):
            start(count+1, choice + [i])


if __name__ == '__main__':
    H = 2
    input = sys.stdin.readline
    T = int(input())
    for t in range(T):
        n = int(input())
        min_time = 9999
        board = [list(map(int, input().split())) for _ in range(n)]
        people, stair = [], []
        init()
        people_num = len(people)

        start(0, [])
        print("#{}".format(t+1), min_time)

https://www.acmicpc.net/problem/14890

https://yabmoons.tistory.com/49

해설은 이 블로그를 참고했다. 

별다른 알고리즘이 사용되지 않지만, 쉽지는 않은 문제이다.

경계값 등 변수값을 정해줄 때 사람 헷갈리게 하는 점이 많기 때문이다...

파이썬으로 이 문제를 풀 때 유의해야 하는 점은 파이썬의 for문은 다른 언어와 다르다는 점이다.

c에서는 for (int i=0; i<n; i++) 하고 for문 내에서 i를 증가시킬 수 있지만,

python에서의 for i in range(n)은 for문 내에서 i 값을 변경시켜도 다음 반복 시 원래 값으로 돌아온다는 것.

이 문제에 적용해보면 다음과 같다. 여기서 한 번 경사로를 지은 곳은 다시 살필 필요가 없다. 쩜프쩜프! 

예를 들어 어떤 행이 [ 3 2 2 1 ]이고 경사로 길이가 2였을 때, 첫 번째 주인공은 3이다.

자, 그러면 2 2 위에 경사로가 지어질 것이고.

그 다음 반복문의 주인공이 되야 하는 것은 첫번째 2를 건너뛰고 바로 두 번째 2 가 된다.

왜냐하면 한 곳 위에 두 개의 경사로가 지어질 수 없다고 문제에 나와있기 때문이다.

(*주의: 바로 1로 가면 안 된다. 이게 이 문제의 헷갈리는 점인데...두번째 2 다음에 1이 나오므로 여기에도 경사로를 지어줘야 하기 때문이다!)

아무튼 그래서 반복문 내에서 다음 주인공 원소를 만들기 위해 점프 점프 할 필요가 있고, 그래서 while문을 썼다.

결론.

이 시뮬레이션 문제는, 

첫째는 평평한 땅을 지날 때 카운트를 증가시켜준다는 것,

두번째는 경계값이나 각종 값 정해줄 때 신경써야 하는 것

이게 핵심인거같다.

import sys


def make_road(board):
    total_road = 0
    for col in range(n):
        can_be_road = True
        flat_num = 1

        row = 0
        while row < n-1:  # 반복문 내에서 row 값을 변경시킬 것이므로 for 대신 while을 쓴다.
            if board[row][col] == board[row+1][col]:  # 같은 값을 유지할 때
                flat_num += 1
                row += 1
            elif board[row][col] + 1 == board[row+1][col]:  # 높은 길을 만났을 때
                if flat_num >= l:  # 경사로 지을 수 있음
                    flat_num = 1  # 초기화
                    row += 1
                else:
                    can_be_road = False # 경사로를 한번 놓을 수 없으면 그 길은 끝
                    break
            elif board[row][col] - 1 == board[row+1][col]:  # 낮은 길을 만났을 때
                standard = board[row+1][col]
                for i in range(l):
                    if row+1+i >= n or standard != board[row+1+i][col]:  # 경사로 범위를 넘어서거나 차이가 1 이상일 때
                        can_be_road = False
                        break
                if can_be_road:
                    flat_num = 0
                    row += l
                else:
                    break
            else:
                can_be_road = False
                break
        if can_be_road:
            total_road += 1

    return total_road


if __name__ == '__main__':
    n, l = map(int, sys.stdin.readline().split())
    board_origin = []
    for _ in range(n):
        board_origin.append(list(map(int, sys.stdin.readline().split())))

    board2_origin = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            board2_origin[i][j] = board_origin[j][i]
    # 세로 길
    print(make_road(board_origin)+make_road(board2_origin))