AndroidTeacher

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

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

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

www.acmicpc.net/problem/12015

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다.

예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이다.

풀이 과정

먼저, 풀이과정 두가지를 이용할 수 있는데,

하나는 이진탐색을 직접 구현하여 수열이 들어갈 자리를 찾는 방법이고

다른 하나는 내장 모듈인 bisect를 이용한 방법이다.

먼저 풀이1번 부터 설명하자면,

array는 문제에서 설명한 수열A를 나타낸다. A에 수열의 모든 원소들을 저장한다.

stack은 정답을 나타낼 가장 긴 증가하는 부분수열을 나타낼 것이다.

for문 부분부터 살펴보면, 수열A를 처음부터 돌면서 수열들을 뽑아내게 되는데

현재 원소가 stack의 마지막 원소보다 크다면, 당연히 수열을 연장할 수 있으므로 stack의 마지막에 추가한다.

하지만 그렇지 않다면? 버려야 할까?

그렇지 않다.

만약, 현재 stack이 10, 20, 40, 60으로 구성되어 있고, 현재 50이 들어갈 자리가 60이 있는 자리인 상황이라면

60을 50으로 교체해야 더 긴 수열을 연장할 수 있다.

왜냐하면, 10, 20, 40, 60 일때 55가 들어온다면 연장할 수 없지만 10, 20, 40, 50 일 경우에는 연장할 수 있기 때문이다.

그래서, else문에 stack[binary_search(i, 0, len(stack) - 1)] = i 라는 조건을 준 것이다.

n = int(input())
array = list(map(int, input().split()))
stack = [0]


def binary_search(target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if stack[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start


for i in array:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[binary_search(i, 0, len(stack) - 1)] = i

print(len(stack) - 1)

다른 풀이과정은 간단하다, 

bisect_left는 리스트에서 i라는 원소가 들어갈 가장 왼쪽 위치를 반환해주는 함수이다.

위 방법과 마찬가지로 stack의 가장 마지막 원소가 현재 진입하려는 원소보다 작으면 뒤로 이어서 붙여주면 되고,

아닌 경우에는 이진탐색을 통해 해당 인덱스의 원소를 교체해주면 된다.

from bisect import bisect_left

n = int(input())
array = list(map(int, input().split()))
stack = [0]

for i in array:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[bisect_left(stack, i)] = i

print(len(stack)-1)

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/1300

문제 설명

이 문제에서 A라는 배열의 각 칸에는 다음과 같이 자기 인덱스의 곱을 담고있다. ( 즉 N[2][3] = 2*3 )

이러한 배열을 B라는 1차원 배열에 오름차순으로 나타내었을 때, k번째 인덱스에는 어떤 수가 있는지를 출력하는 문제이다.

풀이 과정

처음에는 N*N크기의 1차원 배열을 만들어 for문을 이용해 1*1부터 N*N까지의 수를 모두 넣어주고 정렬을 한 후에

그 배열의 k번째 수를 출력하도록 설계하였다.

하지만 문제에서 N은 10^5보다 작거나 같은 자연수이기 때문에 N*N크기의 배열을 만들려면 10^10만큼의 굉장히 많은 메모리가 필요했고 결과도 마찬가지로 메모리 초과가 나왔다.

이러한 큰 메모리 문제가 발생하는 경우의 탐색은 이분탐색으로 접근하면 쉽게 해결할 수 있다.

따라서 많은 고민끝에 다음과 같이 접근하였다.

1) N*N의 모든 수를 구할 필요 없이, 내가 구하고자 하는 K번째 인덱스 까지만 알면 된다.

2) 2차원 배열의 각 칸들의 값은 i*j 형태를 띄므로, 일정한 규칙이 존재한다.

3) 이 규칙에 따르면, 임의의 수 a보다 작거나 같은 수의 개수를 구하는 식이 존재한다.

4) 각 행은 구구단처럼 1단 2단 3단... 식으로 나타나기 때문에 ( a / 행번호 ) 가 그 행에서 구하고자 하는 개수가 된다.

   단, (a / 행번호) 가 N보다 클 경우에는 N이다.

   예를들어, 임의의 수 a를 4라고 했을 때, 1행은 4 / 1 = 4 이지만 N이 3이므로 3개이며

   4 / 2 = 2 이므로 2행은 2개, 4 / 3 = 1 이므로 3행은 1개이다.

이러한 접근방식을 이용하여 이분탐색을 진행하여 내가 구하고자 하는 인덱스를 마주하게 되면 정답이 된다.

이분탐색에서 사용했던 방법 똑같이, 내가 구하고자 하는 target(인덱스)가 mid값(임의의 인덱스)보다 작으면 end값을 줄여 탐색 범위를 좁히면 되고,

target이 mid값보다 크면 start값을 높여 탐색 범위를 좁히면 된다.

n = int(input())
k = int(input())

def binary_search(target, start, end):
    while(start <= end):
        mid = (start + end) // 2

        cnt = 0
        for i in range(1, n+1):
            cnt += min(mid//i, n)

        if cnt >= target:
            end = mid-1
        else:
            start = mid+1
    return start


print(binary_search(k,1,n*n))

https://github.com/HongEunho

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

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