색종이 붙이기 - BOJ

색종이 붙이기 - BOJ

def dfs(x, y, cnt):
    global ret
    if y >= 10:
        ret = min(ret, cnt)
        return
    if x >= 10:
        dfs(0, y + 1, cnt)
        return
    if a[x][y]:
        for p in range(5):
            if paper[p] == 5: # 5개 다 붙였으면 pass
                continue
            if x + p >= 10 or y + p >= 10: # 범위 넘어가면 pass
                continue
            flag = 0
            for i in range(x, x + p + 1):
                for j in range(y, y + p + 1):
                    if not a[i][j]: # 범위가 0이라면
                        flag = 1
                        break
                if flag: break
            if not flag: # 범위에 0이 없다면 (전부 1)
                for i in range(x, x + p + 1):
                    for j in range(y, y + p + 1):
                        a[i][j] = 0

                paper[p] += 1
                dfs(x + p + 1, y, cnt + 1) # 앞뒤로 전부 백트래킹 기법 (최소인 것만 갱신하고 원래 값으로 회복)
                paper[p] -= 1

                for i in range(x, x + p + 1):
                    for j in range(y, y + p + 1):
                        a[i][j] = 1
    else: # 1이 아니면 다음 x
        dfs(x + 1, y, cnt)

a = [list(map(int, input().split())) for _ in range(10)]
paper = [0, 0, 0, 0, 0]
ret = float('inf')
dfs(0, 0, 0)
if ret == float('inf'):
    print(-1)
else:
    print(ret)

삼각 달팽이 - 프로그래머스

삼각 달팽이 - 프로그래머스

def solution(n):

    li = [[0] * n for _ in range(n)]

    ret = []

    x, y = -1, 0

    num = 1

    for i in range(n):

        for j in range(i, n):

            if i % 3 == 0:

                x += 1

            elif i % 3 == 1:

                y += 1

            elif i % 3 == 2:

                x -= 1

                y -= 1

            li[x][y] = num

            num += 1

    for i in li:

        for j in i:

            if j != 0:

                ret.append(j)

    return ret

프렌즈4블록 - 프로그래머스

프렌즈4블록 - 프로그래머스

def dfs(m, n, a):
    global cnt, flag
    li = []
    d = dict()
    for i in range(m - 1):
        for j in range(n - 1):
            if a[i][j] == '0': # 비어 있는 칸이면 pass
                continue
            if a[i][j] == a[i + 1][j] == a[i][j + 1] == a[i + 1][j + 1]: # 2 x 2 블록의 모양이 모두 같다면
                li += [(i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)]
    if not li: # 같은 블록이 하나도 존재하지 않는다면 재귀함수 탈출
        flag = True
        return
    s = set(li)
    cnt += len(s)
    for ele in s:
        d[ele[1]] = d.get(ele[1], []) + [ele[0]] # 열 별로 사라지는 블록의 index를 넣어둠

    tmp_a = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            tmp_a[j][i] = a[i][j]  # 행-열을 열-행 배열로 전환 

    tmp = [i for i in range(m)]
    # 같은 블록 지우고 떨어뜨리기
    for k in d: 
        ret = ""
        ts = "".join(tmp_a[k])
        remain = set(tmp) - set(d[k])
        for r in remain:
            ret += ts[r]
        tcnt = len(tmp) - len(ret)
        ret = '0' * tcnt + ret
        tmp_a[k] = list(ret)

    for i in range(m):
        for j in range(n):
            a[i][j] = tmp_a[j][i]
    if not flag:
        dfs(m, n, a)

cnt = 0
flag = False
def solution(m, n, board):
    a = [list(i) for i in board]
    dfs(m, n, a)
    return cnt

무선 충전 - SWEA

무선 충전 - SWEA

dx = [0, -1, 0, 1, 0]
dy = [0, 0, 1, 0, -1]

def power(u):
    p = [0] * A
    for i in range(A):
        if abs(u[0] - ap[i][1] + 1) + abs(u[1] - ap[i][0] + 1) <= ap[i][2]:
            p[i] = ap[i][3]
    return p

def calculate(p1, p2):
    ret = 0
    if A == 1: return max(p1[0], p2[0])
    for i in range(A):
        for j in range(A):
            if i != j:
                ret = max(p1[i] + p2[j], ret)
    return ret

T = int(input())

for test_case in range(1, T + 1):
    M, A = map(int, input().split())
    ma = list(map(int, input().split()))
    mb = list(map(int, input().split()))
    ap = [list(map(int, input().split())) for _ in range(A)]

    ua = [0, 0]
    ub = [9, 9]
    _sum = 0
    _sum += calculate(power(ua), power(ub))

    for i in range(M):
        ua[0] += dx[ma[i]]
        ua[1] += dy[ma[i]]
        ub[0] += dx[mb[i]]
        ub[1] += dy[mb[i]]
        _sum += calculate(power(ua), power(ub))

    print("#" + str(test_case) + " " + str(_sum))

배열 B의 값 - BOJ

배열 B의 값 - BOJ

문제 예시의 4X4 배열을 예시로 든다면
0, 1, 2, 3행에서 1,2 행을 바꿔도 최대값이 바뀌지 않을 것임.
따라서 (중간 행 중에서 최소값)과 (0행 or 마지막 행) 중에 행을 하나 교환하거나
열에서도 똑같은 작업을 해서 최대값을 구하면 된다.

def calculate(board):
    _sum = 0
    for i in range(N - 1):
        for j in range(M - 1):
            _sum += board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i][j + 1]
    return _sum

def newmap(x, y, rc): # rc -> r인지 c인지
    b = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            b[i][j] = a[i][j]
    if rc:
        for c in range(M):
            b[x][c], b[y][c] = a[y][c], a[x][c]
    else:
        for r in range(N):
            b[r][x], b[r][y] = a[r][y], a[r][x]
    return b

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
row = [0] * N
col = [0] * M
r_min = float('inf')
c_min = float('inf')
min_col, min_row = -1, -1

ret = calculate(a)

# 각 행열 합 계산
for i in range(N):
    for j in range(M):
        row[i] += a[i][j]
        col[j] += a[i][j]

# 최소 크기 행
for r in range(1, N - 1):
    tr = row[r] * 4
    tr -= 2 * (a[r][0] + a[r][M - 1])
    if r_min > tr:
        r_min = tr
        min_row = r

# 최소 크기 열
for c in range(1, M - 1):
    tc = col[c] * 4
    tc -= 2 * (a[0][c] + a[N - 1][c])
    if c_min > tc:
        c_min = tc
        min_col = c

if min_row > 0:
    new = newmap(0, min_row, 1)
    ret = max(ret, calculate(new))
    new = newmap(N - 1, min_row, 1)
    ret = max(ret, calculate(new))

if min_col > 0:
    new = newmap(0, min_col, 0)
    ret = max(ret, calculate(new))
    new = newmap(M - 1, min_col, 0)
    ret = max(ret, calculate(new))

print(ret)

Two Dots - BOJ

Two Dots - BOJ

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def dfs(x, y, cnt):
    global tx, ty, flag
    if flag: return
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= N or ny >= M or a[nx][ny] != a[tx][ty]: # 범위 벗어나지 않고, 색깔이 같을 때만 하도록
            continue
        if not visit[nx][ny]:
            visit[nx][ny] = True # 방문처리 했다가
            dfs(nx, ny, cnt + 1)
            visit[nx][ny] = False # 안한 걸로
        else:
            if cnt >= 4 and tx == nx and ty == ny: # 4번 이상이고 위치가 같을 때 -> 사이클
                flag = True
                return

N, M = map(int, input().split())
a = [list(input()) for _ in range(N)]
visit = [[False] * M for _ in range(N)]
flag = False

for i in range(N):
    for j in range(M):
        if not visit[i][j]:
            tx, ty = i, j
            visit[i][j] = True
            dfs(i, j, 1)
        if flag:
            print("Yes")
            exit(0)

print("No")