AndroidTeacher

문제 설명

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

문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.

일반적인 BFS/ DFS 문제보다 신경써서 구현해야 할 부분들이 훨씬 까다로운 문제이므로

과정을 하나하나 잘 살펴보면서 구현하시는 것을 추천드립니다.

풀이 과정

먼저 두 방법으로 풀면서 코드를 두 가지로 작성해보았습니다.

코드①은 구현해야 할 부분들을 그대로 나열식으로 작성한 코드이며 길이가 좀 더 깁니다.

코드②는 코드①을 좀더 깔끔하고, 중복되는 코드들을 줄여 정리한 코드입니다.

두 코드 모두 접근 방식은 같습니다.

먼저 공통되는 부분인 rotate(회전)함수와 gravity(중력)함수부터 설명드리자면,

rotate는 반시계(왼쪽)방향으로 90도 회전을 해야 하기 때문에

(0, 0) 좌표는 => (n-1, 0) 좌표로 이동을 하게 되고

(0, 1) 좌표는 => (n-2, 0) 좌표로 이동을 하게 됩니다.

이런식으로 직접 행렬을 그려서 비교해보면

(x, y) 좌표는 => (n-1-y, x) 좌표로 이동함을 알 수 있습니다.

gravity는 벽(-1)이나 경계를 만날 때 까지 아래 빈칸으로 계속 쭉 떨어지게 됩니다.

그래서 밑의 행부터 시작하여 차례대로 while문을 통해 내려갈 수 있는 곳 까지 내려가게 해줍니다.

이제 핵심이 되는 BFS 코드(find_group함수)입니다.

풀이①은 문제에서 조건1에 해당하는

크기가 가장 큰 블록 그룹을 찾는다. 
그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 
그 것도 여러개이면 열이 가장 큰 것을 찾는다.

이 부분을 함수 안에 같이 구현을 하였습니다.

while문을 통해 그룹을 지은 다음, 그룹의 크기가 2보다 작으면 그룹을 만들지 않고 return 합니다.

현재 만든 그룹과 최대 그룹을 비교를 해서

현재 만든 그룹이 더 크면 최대 그룹을 바꿔줍니다.

크기가 같다면, 무지개 블록의 수가 많은 블록을 최대 그룹으로 하고

그것마저 같다면 기준행, 열을 비교하여 선정을 하면 됩니다.

이 방법을 모두 find_group 함수 안에 순서대로 작성하였습니다.

코드①

from collections import deque

n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    graph.append(list(map(int, input().split())))


def find_group(a, b):
    visited = [[False] * n for _ in range(n)]
    groupQ = []
    if graph[a][b] == -1 or graph[a][b] == -2:
        return
    if graph[a][b] > 0:
        myColor = graph[a][b]
    else:
        myColor = 0
    cnt = 1
    queue = deque()
    queue.append((a, b))
    visited[a][b] = True
    while queue:
        x, y = queue.popleft()
        groupQ.append((x, y))

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
                continue
            if graph[nx][ny] == -1 or graph[nx][ny] == -2:
                continue
            if graph[nx][ny] > 0:
                if myColor == 0:
                    myColor = graph[nx][ny]
                elif myColor != graph[nx][ny]:
                    continue
            cnt += 1
            queue.append((nx, ny))
            visited[nx][ny] = True

    if cnt < 2:
        return

    global groupCnt, maxQ

    if cnt > groupCnt:
        groupCnt = cnt
        maxQ = groupQ
    elif cnt == groupCnt:
        thisZeroCnt, maxZeroCnt = 0, 0
        for i in range(cnt):
            if graph[groupQ[i][0]][groupQ[i][1]] == 0:
                thisZeroCnt += 1
        for i in range(groupCnt):
            if graph[maxQ[i][0]][maxQ[i][1]] == 0:
                maxZeroCnt += 1
        if thisZeroCnt == maxZeroCnt:
            groupQ.sort(key=lambda x: x[1])
            groupQ.sort(key=lambda x: x[0])
            maxQ.sort(key=lambda x: x[1])
            maxQ.sort(key=lambda x: x[0])
            gx, gy, mx, my = 0, 0, 0, 0
            for i in range(cnt):
                if graph[groupQ[i][0]][groupQ[i][1]] != 0:
                    gx = groupQ[i][0]
                    gy = groupQ[i][1]
                    break
            for i in range(groupCnt):
                if graph[maxQ[i][0]][maxQ[i][1]] != 0:
                    mx = maxQ[i][0]
                    my = maxQ[i][1]
                    break

            if gx > mx:
                maxQ = groupQ
            elif gx == mx:
                if gy > my:
                    maxQ = groupQ

        elif thisZeroCnt > maxZeroCnt:
            maxQ = groupQ

    return


def gravity():
    for i in range(n-2, -1, -1):
        for j in range(n):
            if graph[i][j] != -1:
                tmp = i
                while tmp + 1 < n and graph[tmp+1][j] == -2:
                    graph[tmp+1][j] = graph[tmp][j]
                    graph[tmp][j] = -2
                    tmp += 1


def rotate():
    newGraph = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            newGraph[n - 1 - j][i] = graph[i][j]
    return newGraph


answer = 0

while True:
    groupCnt = 0
    maxQ = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0:
                find_group(i, j)
    if not maxQ:
        break
    answer += len(maxQ)**2
    for x, y in maxQ:
        graph[x][y] = -2
    gravity()
    graph = rotate()
    gravity()
print(answer)

코드 1과 다른 부분은 BFS 코드(find_group함수)입니다.

코드②은 find_group함수에서는 일단 그룹을 형성하여 그 그룹의 크기와 0(무지개)크기, 일반블록+무지개블록의 좌표를 담은 리스트를 반환을 해주었고

이 리스트들을 하나의 큐에 넣은 후에

정렬을 통해 최대 큐(조건에 맞는 큐)를 선정하였습니다.

또한, visited를 함수 안이 아닌 바깥에 선언을 함으로써, 중복으로 형성하는 그룹을 없앴고

대신, 0칸(무지개)은 다음턴에 다른 그룹들과도 형성될 수 있으므로

다시 미방문 처리를 해주어야 합니다.

코드②

from collections import deque

n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    graph.append(list(map(int, input().split())))

def find_group(a, b, color):
    queue = deque()
    queue.append([a, b])

    block_cnt, zero_cnt = 1, 0
    blocks = [[a, b]]
    zeros = []

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
                continue

            if graph[nx][ny] == color:
                visited[nx][ny] = True
                queue.append([nx, ny])
                block_cnt += 1
                blocks.append([nx, ny])

            elif graph[nx][ny] == 0:
                visited[nx][ny] = True
                queue.append([nx, ny])
                block_cnt += 1
                zeros.append([nx, ny])
                zero_cnt += 1

    for x, y in zeros:
        visited[x][y] = False

    return [block_cnt, zero_cnt, blocks + zeros]

def gravity():
    for i in range(n-2, -1, -1):
        for j in range(n):
            if graph[i][j] != -1:
                tmp = i
                while tmp + 1 < n and graph[tmp+1][j] == -2:
                    graph[tmp+1][j] = graph[tmp][j]
                    graph[tmp][j] = -2
                    tmp += 1

def rotate():
    newGraph = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            newGraph[n - 1 - j][i] = graph[i][j]
    return newGraph

answer = 0

while True:
    visited = [[False]*n for _ in range(n)]
    maxQ = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0 and not visited[i][j]:
                visited[i][j] = True
                block = find_group(i, j, graph[i][j])
                if block[0] >= 2:
                    maxQ.append(block)
    print(maxQ)
    maxQ.sort(reverse=True)

    if not maxQ:
        break
    answer += maxQ[0][0]**2
    for x, y in maxQ[0][2]:
        graph[x][y] = -2
    gravity()
    graph = rotate()
    gravity()
    print(graph)
print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

N x M 크기로 구성된 연구소에 바이러스가 퍼졌다.

연구소의 각 칸은 0, 1, 2로 구성되어 있으며 0은 빈 칸, 1은 벽, 2은 바이러스 이다.

바이러스는 벽을 뚫고 확장할 수 없으며 상하좌우에 인접한 빈 칸으로만 확장이 가능하다.

위 그림과 같이 N x M 모양의 연구소(행렬)가 주어지며, 3개의 벽(1)을 세워야 한다.

3개의 벽을 세웠을 때, 안전영역의 크기(0의 개수)의 최댓값을 구하면 된다.

풀이 과정

바이러스는 '2' 이며 상하좌우의 인접한 빈칸(0)으로만 이동이 가능하기 때문에

먼저 '2'인 칸들을 모두 큐에 넣어준 후에,

BFS(너비우선탐색)을 통해 큐에서 하나씩 꺼내 확장시키는 방식으로 진행하면 된다.

2인 칸에서 시작하여 주변의 0인 칸들을 2로 만드는 방식이다.

이 때, 어디에 벽을 세워야 최댓값이 나올지는 알 수 없기 때문에 벽을 세울 수 있는 모든 경우의 수에 대해 수행해봐야 한다.

따라서, (1, 1) 칸 부터 (n, m)칸 까지 중 빈칸을 순서대로 하나씩 3개 선택하여

벽을 세우고 BFS를 수행한 후 벽을 지우고

그 다음칸에 대해 다시 벽을 세우고 BFS를 수행하고 벽을 지우는 방식을 반복해야 한다.

즉, 백트래킹 방식을 이용해 3개의 벽을 모든 칸에 세워본다.

이렇게 진행하면서 최댓값을 저장한 후, 모든 탐색이 끝난 후 최댓값을 출력하면 된다.

이를 파이썬으로 나타낸 코드는 다음과 같다.

from collections import deque
import copy

def bfs():
    queue = deque()
    tmp_graph = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                queue.append((i, j))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if tmp_graph[nx][ny] == 0:
                tmp_graph[nx][ny] = 2
                queue.append((nx, ny))

    global answer
    cnt = 0

    for i in range(n):
        cnt += tmp_graph[i].count(0)

    answer = max(answer, cnt)


def makeWall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makeWall(cnt+1)
                graph[i][j] = 0

n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    graph.append(list(map(int, input().split())))

answer = 0
makeWall(0)
print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

문제에서 주어진 2048 게임을 구현하는 문제이다.

평소의 2048 게임과는 다르게 이동시 새 블록이 추가되지는 않으며

5번 움직였을 때 맵 내의 최대값을 출력하면 된다.

풀이 과정

백트래킹을 이용해 모든 경우의 수에 대해 확인을 해야 하는 브루트포스 문제이다.

움직일 수 있는 방향은 동, 서, 남, 북 4가지 이다.

만약, 동쪽으로 움직인다면 모든 행에 대해 n - 1칸부터 0번째 칸까지 동쪽으로 움직이는 것을 구현한다.

현재 움직이려는 블록의 동쪽 마지노선의 블록이 현재 블록과 같은 수라면

수를 더해준 후 마지노선 칸에 그 수를 넣어주고

현재 블록은 0으로 만들어 다음 블록들이 이동할 수 있도록 만든다.

( 0 0 2 2 = > 0 0 0 4 )

마지노선 블록이 0이라면 그 칸을 현재 블록의 숫자로 대체한 후

현재 블록을 0으로 만든다.

마지노선이 현재 블록과 같은 수가 아니라면, 합칠 수가 없기 때문에 마지노선을 하나 당긴다.

여기서 말하는 마지노선이란, 처음에는 동쪽 가장 끝이 될 것이며

동쪽 가장 끝이 이미 계산이 된 상태라면 -1씩 해주어 마지노선을 하나씩 줄여주는 것을 말한다.

그리고, 동쪽으로 움직인 경우를 만든 후에

서쪽으로 움직일 때는 동쪽으로 움직인 게임판을 이어서 이용하는 것이 아니라

동쪽으로 움직이기 전의 게임판을 서쪽으로 움직여야 하기 때문에

깊은복사(DeepCopy)를 통해 기존 맵을 복사해둔 후에 그 맵을 이동하도록 한다.

이를 코드로 구현하면 다음과 같다.

from copy import deepcopy

n = int(input())

graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

def move(board, dir):
    if dir == 0:  # 동쪽
        for i in range(n):
            top = n - 1
            for j in range(n - 2, -1, -1):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][top] == 0:
                        board[i][top] = tmp
                    elif board[i][top] == tmp:
                        board[i][top] = tmp * 2
                        top -= 1
                    else:
                        top -= 1
                        board[i][top] = tmp

    elif dir == 1:  # 서쪽
        for i in range(n):
            top = 0
            for j in range(1, n):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][top] == 0:
                        board[i][top] = tmp
                    elif board[i][top] == tmp:
                        board[i][top] = tmp * 2
                        top += 1
                    else:
                        top += 1
                        board[i][top] = tmp

    elif dir == 2:  # 남쪽
        for j in range(n):
            top = n - 1
            for i in range(n - 2, -1, -1):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[top][j] == 0:
                        board[top][j] = tmp
                    elif board[top][j] == tmp:
                        board[top][j] = tmp * 2
                        top -= 1
                    else:
                        top -= 1
                        board[top][j] = tmp

    else:
        for j in range(n):
            top = 0
            for i in range(1, n):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[top][j] == 0:
                        board[top][j] = tmp
                    elif board[top][j] == tmp:
                        board[top][j] = tmp * 2
                        top += 1
                    else:
                        top += 1
                        board[top][j] = tmp

    return board


def dfs(board, cnt):
    global ans
    if cnt == 5:
        for i in range(n):
            for j in range(n):
                ans = max(ans, board[i][j])
        return

    for i in range(4):
        tmp_board = move(deepcopy(board), i)
        dfs(tmp_board, cnt + 1)

ans = 0
dfs(graph, 0)
print(ans)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

위의 문제의 그림처럼 N * M 의 보드가 주어졌을 때, 빨간색 구슬을 구멍안에 넣는 게임이다.

파란색 구슬이 구멍안에 들어가서도 안되고,

굴리는 횟수가 10번을 넘어가서도 안된다.

여러가지 제약조건들이 많은 까다로운 BFS 문제이다.

풀이 과정

구슬을 굴리게 되면, 벽이나 구멍에 닿을 때 까지 구슬은 계속 굴러간다.

따라서, 방향 하나를 정했을 때 그 방향으로 계속 굴러가도록 while문을 통해 구슬을 굴려준다.

(코드의 roll함수의 while 부분)

또, 구슬이 굴러가다가 다른색의 구슬과 마주쳤을 경우에는

앞에 있는 구슬이 멈추면 내 구슬은 그 전칸에서 멈추게 되므로

각 구슬의 카운트를 통해 어떤 구슬이 앞에 있던 구슬인지 표기를 해준 후, 순서에 맞게 구슬을 배치하도록 한다.

또한, 4차원 visited 배열을 통해

발생했던 상황은 또 다시 발생하지 않도록 해준다.

2차원이 아닌 4차원 배열을 이용한 이유는

빨간색 구슬의 좌표는 이전과 같을지라도 파란색 구슬의 좌표가 다르다면 다른 상황이기 때문이다.

이를 파이썬 코드로 나타내면 다음과 같다.

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(input()))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]


def roll(x, y, direct):
    cnt = 0

    while graph[x + dx[direct]][y + dy[direct]] != '#' and graph[x][y] != 'O':
        x += dx[direct]
        y += dy[direct]
        cnt += 1

    return x, y, cnt


def bfs(ra, rb, ba, bb):
    queue = deque()
    queue.append((ra, rb, ba, bb, 1))

    while queue:
        rx, ry, bx, by, cnt = queue.popleft()
        visited[rx][ry][bx][by] = True

        if cnt > 10:
            print(-1)
            exit(0)

        for i in range(4):
            nrx, nry, rcnt = roll(rx, ry, i)
            nbx, nby, bcnt = roll(bx, by, i)

            if graph[nbx][nby] != 'O':
                if graph[nrx][nry] == 'O':
                    print(cnt)
                    exit(0)
				
                # 겹쳤을 때, 앞 뒤를 구분하여 재배치
                if nrx == nbx and nry == nby:
                    if rcnt > bcnt:
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]

                if not visited[nrx][nry][nbx][nby]:
                    visited[nrx][nry][nbx][nby] = True
                    queue.append((nrx, nry, nbx, nby, cnt+1))

    print(-1)
    return


rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'R':
            rx = i
            ry = j
        if graph[i][j] == 'B':
            bx = i
            by = j

bfs(rx, ry, bx, by)

ps. 실패 코드

이 코드는 방문했던 지점을 다시 방문하게 되면서 히든 케이스들을 통과하지 못한 코드이다.

참고용으로 첨부해놓았다.

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(input()))

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


def redBall(x, y, direct):
    nx = x + dx[direct]
    ny = y + dy[direct]
    while True:
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            break
        if graph[nx][ny] == '#':
            break
        if graph[nx][ny] == 'O':
            graph[x][y] = '.'
            return -1, -1
        if graph[nx][ny] == 'B':
            bx, by = blueBall(nx, ny, direct)
            if bx == nx and by == ny:
                graph[x][y] = '.'
                graph[nx-dx[direct]][ny - dy[direct]] = 'R'
                return nx - dx[direct], ny - dy[direct]
            if bx == -1 and by == -1:
                print(-1)
                exit(0)

        nx = nx + dx[direct]
        ny = ny + dy[direct]

    graph[x][y] = '.'
    graph[nx - dx[direct]][ny - dy[direct]] = 'R'

    return nx - dx[direct], ny - dy[direct]


def blueBall(x, y, direct):
    nx = x + dx[direct]
    ny = y + dy[direct]
    while True:
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            break
        if graph[nx][ny] == '#':
            break
        if graph[nx][ny] == 'O':
            return -1, -1
        if graph[nx][ny] == 'R':
            rx, ry = redBall(nx, ny, direct)
            if rx == nx and ry == ny:
                graph[x][y] = '.'
                graph[nx - dx[direct]][ny - dy[direct]] = 'B'
                return nx - dx[direct], ny - dy[direct]

        nx = nx + dx[direct]
        ny = ny + dy[direct]

    graph[x][y] = '.'
    graph[nx-dx[direct]][ny-dy[direct]] = 'B'

    return nx - dx[direct], ny - dy[direct]


def bfs(ra, rb, ba, bb):
    queue = deque()
    queue.append((ra, rb, ba, bb, 1))
    res = 1
    while queue:
        rx, ry, bx, by, cnt = queue.popleft()
        if cnt > 10:
            print(-1)
            exit(0)

        for i in range(4):
            nrx, nry = redBall(rx, ry, i)
            nbx, nby = blueBall(bx, by, i)
            if nrx == -1 and nry == -1:
                if nbx == -1 and nby == -1:
                    print(-1)
                    exit(0)
                else:
                    print(cnt)
                    exit(0)
            queue.append((nrx, nry, nbx, nby, cnt+1))

        res = cnt
    return res

rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'R':
            rx = i
            ry = j
        if graph[i][j] == 'B':
            bx = i
            by = j

print(bfs(rx, ry, bx, by))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://programmers.co.kr/learn/courses/30/lessons/81302#fn1

문제 설명

대기실 상태가 그래프(배열)로 주어진다.

응시자 간 간격이 맨하튼 거리 2 이하인 경우를 방역수칙이 안지켜지고 있다고 하며

맨하튼 거리가 2 이상이거나 응시자 사이에 벽이 존재하는 경우 방역수칙을 지키고 있다고 한다.

대기실의 그래프가 주어졌을 때,

방역수칙을 지키고 있는지, 없는지를 확인하는 문제이다.

풀이 과정

이 문제를 카카오테스트에서 직접 풀었을 때는 DFS를 이용하였고

다시 풀 때는 BFS를 이용하였다.

BFS를 이용했을 때가 훨씬 간결하기도 하였고 풀이 방법도 더 좋은 것 같아

BFS를 이용해 풀이를 하려고 한다.

먼저 대기실은 5개 이며

각각의 대기실은 5 x 5 배열로 이루어져 있다.

그리고 1번째 대기실부터 확인해보자.

대기실에 응시자(P)가 발견되면 그 응시자를 기준으로 맨하튼 거리 이내에 BFS를 수행하여

거리두기가 지켜지고 있는지 확인하자.

먼저, bfs함수 내의 visited를 통해 한 번 방문했던 칸은 방문하지 않도록 할 것이다.

한번 더 방문하게 되면 while문을 두 번 돌았을 때, 맨하튼거리 2 이상을 보장하지 못한다.

ex) 오른쪽으로 갔다가 다시 왼쪽으로 오는 경우는 제자리

시작칸을 기준으로 bfs를 수행하며

거리 1(상하좌우) 이내에 'P'(또 다른 응시자)가 발견되면 즉시 False를 리턴하자.

방문한 지점이거나 벽이 있는 경우는 무시하자. ( 아직 거리두기를 침해하지 않았으므로 )

그 외에, 거리 1 이내에 'O'가 있는 경우는 다음 칸을 한 번 더 검사해야 하므로

그 지점을 큐에 넣어주자.

그리고, 처음 응시자(시작점) 기준으로 2바퀴를 돌았을 때는 맨하튼 거리 2를 넘어가게 되므로

이 때까지 False를 리턴하지 않았다면 거리두기를 잘 지킨 것이므로 True를 리턴해준다.

이렇게 각각의 P마다 bfs를 수행하여 그 대기실의 모든 P가 거리두기를 잘 지킨다면

그 대기실에 1을 표시한다.

from collections import deque

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

def bfs(candidate, place):
    queue = deque()
    visited = [[False]*5 for _ in range(5)]
    queue.append(candidate)
    cnt = 0
    
    while queue:
        x, y = queue.popleft()
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if visited[nx][ny]:
                continue
            if place[nx][ny] == 'X':
                continue
            if place[nx][ny] == 'P':
                return False
            queue.append((nx, ny))
        
        cnt += 1
        if cnt == 2:
            return True
    return True
            

def solution(places):
    answer = []
    
    for place in places:
        candidates = deque()
        flag = True
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    candidates.append((i, j))
        
        for candidate in candidates:
            if not bfs(candidate, place):
                flag = False
                break
        
        if not flag:
            answer.append(0)
        else:
            answer.append(1)
        
    return answer

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

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

주어진 숫자와 연산자로 만들 수 있는 수식의 결과값 중 최대값과 최소값을 구하면 됩니다.

풀이 과정

이 문제는 DFS와 백트래킹을 이용했다.

문제에서 연산에 사용할 숫자(A1,A2...An)와 연산자의 개수(b1, b2, b3, b4)가 주어진다.

연산자는 앞에서 부터 차례대로 더하기, 빼기, 곱하기, 나누기 연산자의 개수를 나타낸다

숫자의 순서는 바뀌면 안되며, 연산자의 순서만을 바꿀 수 있다.

따라서, 숫자의 순서는 유지한채 연산자를 더하기, 빼기, 곱하기, 나누기를 써가며 식을 바꿔주면 되므로

첫 번째 숫자에 첫 연산자를 넣고 DFS를 돌린다음

다시 백트래킹을 통해 원래 상태로 돌린 후

두 번째 연산자를 넣고 DFS를 돌린다음 다시 백트래킹으로 원래 상태로 돌려

모든 경우의 수를 찾아내야 한다.

그리고 이 모든 경우의 수 중에 최댓값과 최솟값을 찾아 출력하면 된다.

이를 파이썬 코드로 나타내면 다음과 같다.

n = int(input())
number = list(map(int, input().split()))
op = list(map(int, input().split()))
minR = int(1e9)
maxR = -int(1e9)

answer = number[0]

def dfs(idx):
    global answer
    global minR, maxR

    if idx == n:
        if answer > maxR:
            maxR = answer
        if answer < minR:
            minR = answer
        return

    for i in range(4):
        tmp = answer
        if op[i] > 0:
            if i == 0:
                answer += number[idx]
            elif i == 1:
                answer -= number[idx]
            elif i == 2:
                answer *= number[idx]
            else:
                if answer >= 0:
                    answer //= number[idx]
                else:
                    answer = (-answer // number[idx]) * -1

            op[i] -= 1
            dfs(idx+1)
            answer = tmp
            op[i] += 1


dfs(1)
print(maxR)
print(minR)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

스도쿠가 주어졌을 때, 빈 칸을 채워 스도쿠를 완성하는 문제이다.

풀이 과정

문제를 풀기전에, 스도쿠가 무엇인지에 대해 먼저 알아야 한다.

자세한 설명은 위 백준 문제링크에 나와있지만

9 x 9 맵에서 가로(행)에 1~9까지 모든 숫자가 들어가야 하고 세로(열)에도 1~9까지의 모든 숫자가 들어가야하고

3x3 정사각형에도 1~9까지의 모든 숫자가 들어가야 한다.

그래서 맵이 주어졌을 때

첫 번째 빈 칸부터 시작하여 마지막 빈 칸까지 적절한 수를 넣어가며 스도쿠를 완성시켜야 한다.

그래서 DFS + 백트래킹을 통해

첫 번째 칸에 1~9 숫자를 넣어가며 확인하면 된다.

풀이 방법은 다음과 같다.

① 먼저 문제에서 빈 칸은 0으로 주어지기 때문에

graph의 0인칸의 위치정보(x, y)를 blank 리스트에 넣어준다.

② 첫 번째 빈칸에 1~9까지의 수 중 넣을 수 있는 수를 넣는다.

넣을 수 있는 수는 빈칸의 행,열,3x3정사각형에 없는 수임을 확인하자.

확인이 되면 그 빈칸에는 그 수를 넣어준다.

③ 그 다음 빈칸에 대해서도 같은 방법을 수행한다.

④ 마지막 빈칸까지 채우면 스도쿠를 완성하므로 맵을 출력한다.

import sys
graph = []
blank = []

for i in range(9):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

for i in range(9):
    for j in range(9):
        if graph[i][j] == 0:
            blank.append((i, j))

def checkRow(x, a):
    for i in range(9):
        if a == graph[x][i]:
            return False
    return True

def checkCol(y, a):
    for i in range(9):
        if a == graph[i][y]:
            return False
    return True

def checkRect(x, y, a):
    nx = x // 3 * 3
    ny = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if a == graph[nx+i][ny+j]:
                return False
    return True


def dfs(idx):
    if idx == len(blank):
        for i in range(9):
            print(*graph[i])
        exit(0)

    for i in range(1, 10):
        x = blank[idx][0]
        y = blank[idx][1]

        if checkRow(x, i) and checkCol(y, i) and checkRect(x, y, i):
            graph[x][y] = i
            dfs(idx+1)
            graph[x][y] = 0

dfs(0)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

• N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
• N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

풀이 과정

체스판의 퀸은 자신의 줄, 칸, 대각선에 위치한 말을 잡을 수 있다.

이러한 퀸을 N x N의 체스판에 N개 놓을 때 서로 공격할 수 없도록 놓아야 한다.

이 문제는 퀸의 위치를 바꾸어가며 경우의 수를 구하는 DFS+백트래킹 문제이다.

일단 퀸은 한 줄에 1개밖에 놓지 못하므로

2차원배열이 아닌 1차원 배열을 만들어

각 배열의 칸에는 그 행의 퀸의 위치를 넣는다.

그리고 퀸이 같은 열에 존재하거나 같은 대각선에 존재하는지를 확인하여

존재하지 않는다면 퀸을 놓음으로써 경우의 수를 늘려간다.

n = int(input())
queen = [0] * n
result = 0

def isAdjecent(idx):
    for i in range(idx):
        if queen[idx] == queen[i] or abs(queen[idx] - queen[i]) == idx - i:
            return False

    return True

def dfs(idx):
    if idx == n:
        global result
        result += 1
        return

    for i in range(n):
        queen[idx] = i
        if isAdjecent(idx):
            dfs(idx + 1)

dfs(0)
print(result)

현재 이 코드는 시간초과가 난다. (조건이 더 추가된 것 같음)

파이썬으로는 시간초과를 해결하려면 더 많은 배열을 추가하여 다른 조건들을 넣어주어야 한다고 한다.

현재 문제는 15x15문제로 정답이 정해져있으니

시간초과가 해결되지 않는다면 다음 코드를 제출하는 것을 추천한다(야매)

answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(answer[int(input())])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !