Awesome

http://boj.kr/14501 

DP로도 풀 수 있고, 완전탐색(DFS)로도 풀 수 있다. N이 최대 15이므로 완전탐색으로 풀어도 문제가 없다.

하지만 항상 중요한건 아이디어로,

완전탐색으로 풀 수 있는 아이디어를 얻었다면 조금만 더 시간을 쓰면 DP로도 풀 수 있을 것이다.

완전탐색(DFS)에서도 DP와 같이 주요 해결 실마리는 해당 day를 선택하지 않음 vs 선택함이다.

문제에서는 1일부터라고 나와있지만 취향따라 0부터 시작하기로 했다.

위 그래프는 DFS 트리를 그려본 것이다. (0일, 0원)에서 시작해서

왼쪽은 (0일에 일하지 않고 +1일, 여전히 0원)

오른쪽은 (0일에 일하고 +3일, 0일 상담비) 를 의미한다.

함수가 저런식으로 양쪽으로 진행된다는 것을 보여주기 위함이다.

경계값 때문에 조금 헷갈리는 문제인데, 그럴 때는 직접 대입해보자.

N이 10으로 주어졌다고 해보자. 배열은 0부터 시작하므로 마지막 상담일자는 9일이 될 것이다.

그래프 옆에 적어뒀듯이 함수 내에서 dfs(day, total) 에서 day는 상담을 시작하는 날짜이므로 기저사례에 해당하는 것은 day = N 인 경우이다. 9일이 마지막 근무일이었는데 10일에 상담을 시작할 수는 없기 때문이다.

이렇게 생각하면 마지막 근무일을 넘겼는데도 day에 10을 넣어서 dfs를 호출하는것 자체가 이상하게 보일수가 있는데, 그럴 땐 그 날을 정산하는 날짜(max_total = max(max_total, total) & return )라고 생각하자. 저 정산 과정(기저사례처리)이 필요하기 때문!

import sys


def dfs(day, total):
    global max_total

    # 기저 사례: 일하러 갈 수 있니?
    if day >= N:
        max_total = max(max_total, total)  # 마지막 day는 정산하는 날
        return

    # 일하러 가라
    dfs(day+1, total)  # 선택 X
    if day + T[day] <= N:
        dfs(day+T[day], total+P[day])  # 선택하고 해당 일로 점프


input = sys.stdin.readline
max_total = 0
N = int(input())  # 퇴사일
T, P = [0] * N, [0] * N  # T=time, P=pay (입력)
for i in range(N):
    T[i], P[i] = map(int, input().split())
dfs(0, 0)  # 0 ~ N일까지의 최댓값
print(max_total)

http://boj.kr/14501 

페이의 최댓값을 구하려면 각각의 모든 날짜에 대해서 선택을 하거나 / 하지 않거나 모든 경우를 고려해 봐야 한다.

점화식

d[n] = max(d[n+1], d[n+T[n]] + P[n])

=

N~n일까지의 최대 페이 = max(N~n+1일까지의 최대 페이, N~n+T[n]까지의 최대 페이+n일의 페이)

=

N~n일까지의 최대 페이 = max(n일에 일을 하지 않았을 때, n일에 일을 했을 때)

즉 d[i]가 0일부터 i일까지의 페이가 아니라 i일부터 N일까지의 페이라고 생각해야 한다.

N~i일의 페이라고 생각하면 편하다. 미래에서 돌아온다고 생각.

다시한번 점화식의 의미를 하나하나 살펴보면 다음과 같다.

N : 문제에서 주어진 퇴사 전날

d[n] : N일부터 n일까지의 최대 페이 (n이 1이면 문제의 답이 된다)

d[n+1] : n일에 일을 하지 않았을 때의 페이. n일에 일을 하지 않았으므로 N일~n일의 페이 = N일~n+1일의 페이

d[n+T[n]] : N일~n+T[n]일까지의 페이. 

T[n] : n일에 있는 상담에 걸리는 시간

예를 들어 문제에서 주어진 대로 이렇게 표가 있다고 했을 때 (N=7)

답을 구하려면

d[1] = max(d[2], d[1+T[1]] + P[1]) = max(d[2], d[4] + 10) 이 된다.

7일~1일까지의 최대 페이를 구하려면

7일~2일까지의 페이 + 1일에는 쉼

7일~4일까지의 페이 + 1일에 맡은 상담을 함(10원을 받음)

둘 중에 큰 것을 선택해야 하기 때문이다.

+ 추가 설명

d[n] = max(d[n+1], d[n+T[n]] + P[n])

n일에 일을 하지 않은 게 d[n+1]이라는 건 이해하기 쉬운데,

일을 한 것이 d[n+T[n]] + P[n] 이라는 게 이해가 잘 되지 않았다. 일단 괄호가 많아서 눈에 잘 들어오지도 않는다.

풀어서 말하면 d[n + 상담일수] + n일의 상담 페이 라는 뜻이다. 

점화식 우변 max()에 안에 있는 두 값을 그림으로 다시 보자. 이번엔 n 대신 a를 써 보자.

이게 a일에 일을 하지 않았을 때를 의미하는 d[a+1]다.

빨간색은 그 사이에 벌어들인 돈이다. a일에 일을 하지 않았으므로 0원+d[a+1]이다.

이건 d[a+T[a]] + P[a] 이다. 그림 순서대로 보면 P[a] + d[a + T[a]] 이다.

마찬가지로 빨간 글씨는 페이, 그 사이 벌어들인 돈이다. 

뒤에 있는 파란 네모는 d[a + T[a]] 인데,

아직 모르므로 재귀를 호출해서 알아낼 수 있을 때까지 간 다음, 다시 d[1]로 돌아오면 답을 알아낼 수 있다.

(알아낼 수 있을 때까지=d[N]이다)

http://boj.kr/15685 

규칙을 찾아내면 되는 문제이다.

(x, y) 증가량으로 규칙을 찾아내려고 하면 눈에 잘 보이지 않는다.

문제에서 제시한 

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

를 사용한다.

0세대에서부터 K세대까지 직접 그려보는데,

새로 생겨난 변의 번호를 직접 써보면 규칙이 보인다.

K세대 드래곤 커브의 각 선분 정보를 담은 리스트를 directions 라고 하면,

K+1세대 드래곤 커브의 것은 directions을 역순으로 하고 (x+1)%4 한 것이다.

import sys


# 네 꼭짓점이 모두 드래곤 커브인 정사각형 갯수 구하기
def calc():
    ret = 0
    for i in range(SZ):
        for j in range(SZ):
            if j < SZ - 1 and i < SZ - 1:
                if board[i][j] and board[i + 1][j] and board[i][j + 1] and board[i + 1][j + 1]:
                    ret += 1
    return ret


def draw(x, y, d, generation):
    # draw 0st dragon
    directions = [d]
    board[x][y] = 1
    x += dx[d]
    y += dy[d]
    board[x][y] = 1

	# draw Kst dragons
    for g in range(1, generation + 1):
        tmp = []  # 이번 세대에 새로 생긴 선분들의 방향
        for d in reversed(directions):  # 역순
            d = (d + 1) % 4
            tmp.extend([d])
            x += dx[d]
            y += dy[d]
            board[x][y] = 1
        directions.extend(tmp)  # directions 업데이트


SZ = 101  # 전체 좌표의 크기. 0 <= x, y <= 100 이므로 크기는 101이 되어야 함
input = sys.stdin.readline
N = int(input())
all_curves = [list(map(int, input().split())) for _ in range(N)]
board = [[0] * SZ for _ in range(SZ)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for x, y, d, g in all_curves:  
    draw(y, x, d, g)  
    # 문제에서의 (x, y) = (col, row)이므로 여기서만 거꾸로 전달하고
    # 나머지 보드 위에서의 움직임은 원래 하던 row, col으로 하면 된다.

print(calc())

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/16236 

가장 가까운 물고기는 BFS로 찾는다. 코드 내에서 fishes 리스트가 그것이다.

새로운 물고기를 먹을 때마다 상어의 위치가 변경되므로 fishes 리스트를 매번 갱신한다.

itemgetter를 이용해 물고기를 거리, row, col 순으로 손쉽게 정렬해줄 수 있다.

상어의 크기가 증가하는 규칙이 상어의 크기 += 물고기의 크기가 아니라,

상어 크기=지금까지 먹은 누적 물고기 갯수(in_belly) 일때마다 상어의 크기가 1씩 늘어난다는 점에 유의하자. 당연히 상어 크기가 늘어났으면 in_belly를 0으로 초기화해야 답이 나온다.

import sys
from collections import deque
from operator import itemgetter


def get_distance(shark):
    fishes = []
    visited = [[0] * N for _ in range(N)]
    visited[shark[ROW]][shark[COL]] = 1
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    queue = deque([[shark[ROW], shark[COL], 0]])
    while queue:
        r, c, dist = queue.popleft()
        for i in range(4):
            next_r = r + dx[i]
            next_c = c + dy[i]
            if 0 <= next_r < N and 0 <= next_c < N:
                if not visited[next_r][next_c]:
                    if board[next_r][next_c] <= shark[SIZE]:  # 지나갈 수 있는 물고기
                        if 0 < board[next_r][next_c] < shark[SIZE]:  # 먹을 수 있는 물고기
                            fishes.append([next_r, next_c, board[next_r][next_c], dist+1])
                        visited[next_r][next_c] = 1
                        queue.append([next_r, next_c, dist+1])

    fishes.sort(key=itemgetter(DIST, 0, 1))  # 거리, row, column 순으로 정렬
    return fishes


def start(shark):
    global in_belly
    
    sec = 0
    while True:
        fishes = get_distance(shark)
        if not fishes:  # 물고기가 없으면 종료
            print(sec)
            break
        prey = fishes[0]  # 희생양 물고기

        in_belly += 1
        if shark[SIZE] == in_belly:
            shark[SIZE] += 1
            in_belly = 0

        shark = [prey[ROW], prey[COL], shark[SIZE]]  # 상어 정보 업뎃
        board[prey[ROW]][prey[COL]] = 0
        sec += prey[DIST]
        del fishes[0]
    return


if __name__ == '__main__':
    ROW, COL, SIZE, DIST = 0, 1, 2, 3
    input = sys.stdin.readline
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    shark_sz = 2  # 상어의 기본 크기는 2
    in_belly = 0  # 누적된 먹은 물고기 갯수
    
    for i in range(N):
        for j in range(N):
            if board[i][j] == 0:
                continue
            elif board[i][j] == 9:  # 상어
                shark_init = [i, j, shark_sz]
                board[i][j] = 0  # 나중에 물고기로 착각하지 않도록 0으로 변경

    start(shark_init)

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/2178

import sys
import collections


def Print(lst):
    for i in lst:
        for j in i:
            print(j, end=' ')
        print("")
    print("")


def bfs(i, j):
    visited = [[0 for _ in range(m)] for _ in range(n)]
    x = [0, 0, 1, -1]
    y = [1, -1, 0, 0]

    queue = collections.deque([[i, j, 1]])
    visited[i][j] = 1
    while queue:
        r, c, depth = queue.popleft()
        for dir in range(4):
            nR = r + x[dir]
            nC = c + y[dir]
            if 0 <= nR < n and 0 <= nC < m:
                if nR == n-1 and nC == m-1:
                    return depth+1
                if board[nR][nC] == 1 and not visited[nR][nC]:
                    visited[nR][nC] = 1
                    queue.append([nR, nC, depth+1])

        # Print(visited)


if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    board = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        tmp = sys.stdin.readline()[:-1]
        for j in range(m):
            board[i][j] = int(tmp[j])

    #Print(board)
    print(bfs(0, 0))