AndroidTeacher

programmers.co.kr/learn/courses/30/lessons/43163#

문제 설명

두개의 단어 begin과 target이 주어지며 단어의 집합 words가 주어집니다.

begin은 words에 있는 단어 중 하나로 변경 가능하며, 한 번에 하나의 알파벳만 변경가능합니다.

이러한 과정을 통해 target까지 가는데 몇 단계의 과정을 거쳐야 하는지를 출력하면 됩니다.

문제의 자세한 설명은 위 링크에 나와있습니다!

풀이 과정

문제에서 한 번에 하나의 알파벳만 변경가능하다고 했으므로,

단계별로 현재 선택한 단어와 한 글자 차이가 있는 알파벳만 모두 얻도록 하는 BFS 를 이용하면 됩니다.

첫 begin을 예로 들면, begin과 단 한 글자 차이만 있는 단어들을 모두 stack에 넣습니다.

이렇게 모두 stack에 넣고 나면 1단계가 완성이 됩니다.

2단계에서는 이 1단계에 넣은 단어들과 단 한 글자 차이만 있는 단어들을 tack에 넣게 됩니다.

그럼 이 단어들은 begin과는 2 글자 차이가 날 것이고, 현재 비교하는 것들과는 1 글자 차이가 날 것입니다.

이러한 식으로, 단계별로 탐색을 해나가는 bfs방식을 통해 stack에서 꺼낸 원소가 target과 일치하는지 확인하면 됩니다.

def bfs(begin, target, words, visited):
    count = 0
    stack = [(begin, 0)]
    while stack:
        cur, depth = stack.pop()
        if cur == target:
            return depth
        
        for i in range(len(words)):
            if visited[i] == True:
                continue
            cnt = 0
            for a,b in zip(cur, words[i]):
                if a!=b:
                    cnt += 1
            if cnt == 1:
                visited[i] = True
                stack.append((words[i], depth+1))
                
            

def solution(begin, target, words):
    answer = 0
    if target not in words:
        return 0

    visited = [False]*(len(words))

    answer = bfs(begin, target, words, visited)

    return answer

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/1707

문제 설명

문제에서 말한 이분그래프란, 그래프 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 말한다.

즉, 그래프의 정점을 두가지 색으로 칠할 때, 인접한 정점끼리는 다른 색을 가지고 있는 그래프 인 것이다.

위 그림은 대표적인 이분그래프이다.

풀이 과정

visited[V]에 1, 2의 값을 줌으로써 정점의 색을 구분한다. ( 단, 아직 미방문 정점은 0 )

BFS를 수행하기 전에 인접행렬로 그래프를 만들어 준다.

그리고 탐색을 수행하면 되는데, 이 때 주의해야 할 점이 있다.

바로, 비연결 그래프에 대해서도 고려를 해야 한다는 점이다.

연결 그래프의 경우에는 시작점에서 BFS를 수행하면 모든 정점을 탐색할 수 있지만,

비연결 그래프의 경우에는 시작점과 연결되지 못한 정점은 아직 탐색을 수행하지 않기 때문이다.

그래서 아래 코드의 "for k in range(1, V + 1): " 를 통해 모든 정점에서 BFS를 한 번씩 수행하도록 하였다.

from collections import deque

k = int(input())


def bfs(graph, start):
    queue = deque()
    queue.append(start)
    if visited[start] == 0:
        visited[start] = 1  # 이분은 1, 2로 하고 아직 방문하지 않은곳은 0으로 표시
    while queue:
        v = queue.popleft()

        color = visited[v]
        for i in graph[v]:  # V정점과 연결된 모든 정점 확인
            if visited[i] == 0:  # 아직 한번도 방문하지 않음
                queue.append(i)  # 다음에 방문할 곳으로 지정
                if color == 1:  # 현재의 정점과 다른 색상으로 색칠
                    visited[i] = 2
                else:
                    visited[i] = 1
            elif visited[i] == 1:
                if color == 1:
                    print("NO")
                    return False
            elif visited[i] == 2:
                if color == 2:
                    print("NO")
                    return False
    return True


for i in range(k):
    flag = 0
    V, E = map(int, input().split())
    graph = [[] for _ in range(V + 1)]
    visited = [0] * (V + 1)
    for j in range(E):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    for k in range(1, V + 1): # 연결그래프일 경우에는 시작점에서 한번의 BFS를 수행하면 되지만 비연결그래프의 경우에는 모든 정점을 탐색해야 한다.
        if not bfs(graph, k):
            flag = 1
            break
    if flag == 0:
        print("YES")

https://github.com/HongEunho

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

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

문제 설명

www.acmicpc.net/problem/7562

체스판 위의 나이트가 최소 몇번을 움직여 도착지까지 이동할 수 있는지를 구하는 문제이다.

풀이 과정

나이트가 이동할 수 있는 경로는 체스의 나이트와 똑같이 가로2칸 이동후 세로1칸 혹은 가로1칸 이동 후 세로1칸 이기 때문에 8가지 상황이 발생한다.

visited의 각 칸에는 그 칸까지 오는데 필요한 횟수가 저장되어 있으며 초기는 모두 0으로 저장되어 있다.

즉, 아직 밟지않은 칸은 모두 0으로 초기화를 해준 것이다.

단, 시작점은 이미 밟고있기 때문에 1로 표시를 해주며, 도착 칸에서 -1을 해줌으로써 해결할 수 있다.

from collections import deque

dx = [+2, +1, -1, -2, -2, -1, +1, +2]
dy = [+1, +2, +2, +1, -1, -2, -2, -1]


def bfs(a, b, c, d):
    queue = deque()
    queue.append((a, b))

    while queue:
        curX, curY = queue.popleft()
        if curX == c and curY == d:
            print(visited[curX][curY] - 1)
            return True

        for i in range(8):
            nx = curX + dx[i]
            ny = curY + dy[i]
            if nx < 0 or nx >= l or ny < 0 or ny >= l:
                continue
            if visited[nx][ny] == 0:
                visited[nx][ny] = visited[curX][curY] + 1
                queue.append((nx, ny))

    return False


n = int(input())
for i in range(n):
    l = int(input())
    visited = [[0] * l for _ in range(l)]
    a, b = map(int, input().split())
    c, d = map(int, input().split())
    visited[a][b] = 1
    bfs(a, b, c, d)

https://github.com/HongEunho

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

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

문제 설명

www.acmicpc.net/problem/2206

N×M의 행렬로 표현되는 맵에서 0은 이동할 수 있는칸, 1은 벽(이동할 수 없는 칸)을 나타낸다.

단, 벽을 부수고 이동할 수 있는 기회가 1번 주어지므로 부셨을 때 이동경로가 짧아진다면 부셔도 된다.

(1, 1)에서 시작하여 (N,M)까지 가는데 최단거리를 출력하면 된다.

풀이 과정

전형적인 BFS 의 경로찾기 문제에 벽을 부술 수 있다는 특징이 포함된 문제이다.

중간에 벽을 단 한번만 부술 수 있기 때문에 벽을 부쉈는지의 여부를 3차원 행렬로써 나타내면 된다.

벽 부수기 없이 나타낸다면 visit[x][y] 라고 표현할 수 있지만 z를 추가함으로써 0은 안부숨, 1은 부숨을 표현할 수 있다.

즉, visited[x][y][0]은 안부순 경로, visited[x][y][1]은 부순 경로.

중간에 벽을 부순 경로는 그 이후의 경로부터는 벽을 지나갈 수 없으므로 벽이 아닌곳들만 탐색하면 되고,

중간에 벽을 부수지 않은 경로는 그 이후의 경로에서 벽을 부술 수 있는 선택권이 주어진다.

벽을 부술 수 있는 기회는 단 1번이고, 부술 지 말지를 선택할 수 있기 때문에

앞에서 if graph[nx][ny] == 1 and c == 0 : 처리를 해버리면, 무조건 앞에 나타나는 벽만 부수게 되는 것이 아니냐고 생각할 수 있는데, 같은 for문 안에서 4방향으로 이동하는 상황이고 그 중 다른방향으로 이동하는 것이 자동으로 벽을 부수지 않는 방향이기 때문에 상관 없다.

자세한 코드는 다음과 같다. 

from collections import deque

n, m = map(int, input().split())
graph = []

# 3차원 행렬을 통해 벽의 파괴를 파악함. visited[x][y][0]은 벽 파괴 가능. [x][y][1]은 불가능.
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1

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

# 상하좌우
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(x, y, z):
    queue = deque()
    queue.append((x, y, z))

    while queue:
        a, b, c = queue.popleft()
        # 끝 점에 도달하면 이동 횟수를 출력
        if a == n - 1 and b == m - 1:
            return visited[a][b][c]
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 다음 이동할 곳이 벽이고, 벽파괴기회를 사용하지 않은 경우
            if graph[nx][ny] == 1 and c == 0 :
                visited[nx][ny][1] = visited[a][b][0] + 1
                queue.append((nx, ny, 1))
            # 다음 이동할 곳이 벽이 아니고, 아직 한 번도 방문하지 않은 곳이면
            elif graph[nx][ny] == 0 and visited[nx][ny][c] == 0:
                visited[nx][ny][c] = visited[a][b][c] + 1
                queue.append((nx, ny, c))
    return -1


print(bfs(0, 0, 0))

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/1697

문제 설명

수빈이는 동생과 숨바꼭질을 한다. 수빈이의 좌표는 N, 동생의 좌표는 K이다.

수빈이의 위치가 X일 때, 1초 후에 X+1, X-1 X*2 중에 하나로 이동할 수 있다.

수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지를 구하면 된다.

풀이 과정

BFS를 이용하여 풀었다. 변수에 대해 먼저 설명하자면, count는 일 수, flag는 찾은 여부를 나타내는 변수이다.

today_queue는 오늘 안에 도착할 지점, queue는 내일 방문할 지점 이라고 생각하면 된다.

과정은 다음과 같다.

1) queue에 시작점을 넣어주고 시작점을 visit처리 한다.

2) queue에 원소가 남아있을 때 까지 bfs를 돌린다. ( 시작 시는 1개 )

3) bfs안에서 today_queue를 만들어 queue에 있는 원소들을 모두 가져온다.

4) 오늘 할당량을 모두 비울 때 까지 숨바꼭질을 진행하며 내일 방문할 곳은 queue에 삽입한다.

5) 오늘 방문할 지점에 동생의 좌표가 존재하면 flag = 1 처리를 하고 탈출한다.

from collections import deque
import copy

n, k = map(int, input().split())
visited = [False] * 100001
count = 0
flag = 0

def bfs():
    global count
    today_queue = copy.deepcopy(queue)

    while today_queue:
        x = today_queue.popleft()
        queue.popleft()
        if x == k:
            global flag
            flag = 1
            return
        for i in range(3):
            if i == 0:
                nx = x + 1
            elif i == 2:
                nx = x - 1
            else:
                nx = x * 2
            if nx < 0 or nx > 100000:
                continue
            if not visited[nx]:
                queue.append(nx)
                visited[nx] = True

    count += 1


queue = deque()
queue.append(n)
visited[n] = True

while queue:
    bfs()
    if flag == 1:
        print(count)
        break

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/7569

문제 설명

가로 M, 세로 N 의 토마토 상자가 H높이만큼 쌓여져 있다. 즉 3차원 배열의 형태로 쌓여져 있다.

이 토마토는 보관 후 하루가 지나면 익은 토마토들의 인접(상하좌우위아래)한 토마토들이 모두 익게 된다.

이 토마토들이 모두 익게되는데 며칠이 걸리는지 최소 일수를 구하면 된다.

풀이 과정

토마토들의 좌표는 graph[x][y][z]로 나타낼 수 있다. 기존 문제들과의 차이점이라고 한다면, 보통 BFS문제는 2차원적인 문제가 많이 나오다 보니 방향을 상하좌우만 신경을 쓰면 되었지만, 이 문제는 3차원 문제이므로 위 아래로 방향을 추가해 주어야 한다.

코드에서,

today_queue는 오늘 익게 된 토마토들의 좌표들을 저장하는 큐이다.

next_queue는 내일 익게 될 토마토들의 좌표들을 저장하는 큐이다.

먼저 find_start()를 통해 제일 처음에 익은 토마토들의 위치를 찾아낸 후에, next_queue의 첫 좌표로 저장한다.

0일(카운트 시작 전날)에 이미 익은 토마토들을 저장하는 것이다.

그리고 그 지점들로부터 BFS를 수행하며 count를 하나씩 높여준다. (count는 일 수)

방식은 전날의 next_queue를 today_queue로 복사하여 오늘의 할당량을 준비한다.

그리고 오늘의 할당량에서 하나씩 꺼내며 탐색을 한다. ( 이 때, next_queue에서도 꺼내주어야 한다. 그렇지 않으면 다음날도 똑같은 자리에서 재탐색 하므로)

탐색을 하며 주변에 아직 익지않은 토마토들의 상태를 익은 상태로 변경해주고 그 토마토들의 좌표들을 next_queue에 저장해주는 방식이다.

from collections import deque
import copy

m, n, h = map(int, input().split())
graph = [[] for _ in range(h)]

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

next_queue = deque()
count = 0
flag = 0

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

def find_start():
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 1:
                    next_queue.append((i, j, k))

def bfs():
    global count
    today_queue = copy.deepcopy(next_queue)

    while today_queue:
        x, y, z = today_queue.popleft()
        next_queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= n or nz < 0 or nz >= m:
                continue
            if graph[nx][ny][nz] == 0:
                graph[nx][ny][nz] = 1
                next_queue.append((nx, ny, nz))
    count += 1


find_start()
while next_queue:
    bfs()

for i in range(h):
    for j in range(n):
        if 0 in graph[i][j]:
            flag = 1

if flag == 1:
    print(-1)
else:
    print(count-1)

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/1987

문제 설명

R x C 크기의 보드판이 있다. 이 보드판의 각 칸에는 대문자 알파벳이 하나씩 적혀있으며, 이 보드판을 움직이는 말은 현재 (1,1)에 위치하고 있다. (시작점에 위치)

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있으며, 새로 이동하는 칸에 적힌 알파벳은 지금까지 지나온 알파벳과 겹쳐서는 안된다. 즉, 같은 알파벳 칸을 두 번 이상 지나갈 수 없다.

좌측 상단부터 시작하여 말이 최대 몇 칸을 지날 수 있는지를 출력하면 된다.

풀이 과정

이 문제는 DFS와 BFS 두 방법 모두 이용하여 풀어보았다. 먼저 이 오늘은 DFS로 푼 방법을 소개하려고 한다.

이 문제에서의 핵심은 DFS를 실행할 때는 가는 경로를 체크하면서 가다가 돌아올 때 다시 체크해제를 해주어야 한다. 

그래야 다른 경로들도 탐색하여 최댓값을 구할 수 있기 때문이다.

import sys

r, c = map(int, input().split())
graph = []
myStep = [0]*26
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
count = 0


def dfs(x, y, incnt):
    if x < 0 or x >= r or y < 0 or y >= c:
        return False
    global count
    count = max(incnt, count)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < r and 0 <= ny < c) and not myStep[ord(graph[nx][ny]) - ord('A')]:
            myStep[ord(graph[nx][ny]) - ord('A')] = 1
            dfs(nx, ny, incnt + 1)
            myStep[ord(graph[nx][ny]) - ord('A')] = 0


for i in range(r):
    graph.append(list(sys.stdin.readline().strip()))
    
myStep[ord(graph[0][0]) - ord('A')] = 1
dfs(0, 0, 1)
print(count)

여기서, 사실 처음에는 myStep이라는 리스트에 알파벳들을 그대로 삽입하여 지나온 알파벳인지 검색하는 부분을

graph[nx][ny] not in myStep 로 이용하였다. 하지만 계속 시간초과가 발생하여 하나하나 고치다 보니 이 부분에서 시간초과 문제가 발생한 것을 깨달았고, 위의 코드처럼 myStep에 26칸(대문자 알파벳은 26개이므로)을 미리 만들어 준 후에, A를0으로 시작하여 Z까지 각 칸의 방문여부를 0, 1로 체크하도록 변경하였다. 그리고 통과할 수 있었다.

https://github.com/HongEunho

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

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