AndroidTeacher

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

문제 설명

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

풀이 과정

1부터 n까지의 수 중, 중복없이 m개의 수를 나열하는 문제이다.

즉, 1부터 n까지의 수 중 m개의 수를 나열하는 중복을 허락하지 않는 순열이다.

단, 수열은 오름차순으로 정렬되어야 한다.

예를 들어, n = 4, m = 2일 경우

1부터 4까지의 수 중, 작은 수 부터 시작하여 2개의 수를 중복없이 나열하는 방법은

(1, 2), (1, 3), (1, 4), (2, 1), (2, 3) ... (4, 3) 이다.

이 때, (2, 1), (3, 1), (3, 2) ... 는 오름차순이 아니기 때문에 제외해야 한다.

이를 위해서는 DFS(깊이우선탐색)을 통해 1부터 탐색을 하면 된다.

다만 백트래킹을 통해 방문한 후에는 다시 방문X 처리를 해주어 다음 턴에도 방문할 수 있도록 해야 한다.

깊이 3를 예로 들면,

1 -> 2 -> 3 의 수열을 만든 후에

1 -> 2 -> 4 의 수열을 만들어야 하는데

앞의 2을 방문하고 수열을 만든 후에 방문X 처리를 하지 않으면

1 -> 2 -> 4 의 수열은 2을 방문하지 못하기 때문이다.

이렇게 DFS와 백트래킹을 이용하는 방법과

또, 순열(permutation)을 이용하는 방법이 있는데

이 문제의 의도는 백트래킹을 이용하는 것이므로 백트래킹을 이용해 풀어보길 추천한다.

n, m = map(int, input().split())

visited = [False] * (n + 1)
answer = []


def dfs(start, a):
    if a == 0:
        print(" ".join(map(str, answer)))
        return

    for i in range(start, n + 1):
        if not visited[i]:
            answer.append(i)
            visited[i] = True
            dfs(i, a - 1)
            answer.pop()
            visited[i] = False


dfs(1, m)

https://github.com/HongEunho

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

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

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

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

풀이 과정

1부터 n까지의 수 중, 중복없이 m개의 수를 나열하는 문제이다.

즉, 1부터 n까지의 수 중 m개의 수를 나열하는 중복을 허락하지 않는 순열이다.

예를 들어, n = 4, m = 2일 경우

1부터 4까지의 수 중, 작은 수 부터 시작하여 2개의 수를 중복없이 나열하는 방법은

(1, 2), (1, 3), (1, 4), (2, 1), (2, 3) ... (4, 3) 이다.

이를 위해서는 DFS(깊이우선탐색)을 통해 1부터 탐색을 하면 된다.

다만 백트래킹을 통해 방문한 후에는 다시 방문X 처리를 해주어 다음 턴에도 방문할 수 있도록 해야 한다.

깊이 4를 예로 들면,

1 -> 2 -> 3 -> 4 의 수열을 만든 후에

1 -> 2 -> 4 -> 3 의 수열을 만들어야 하는데

앞의 3을 방문하고 수열을 만든 후에 방문X 처리를 하지 않으면

1 -> 2 -> 4 의 수열은 3을 방문하지 못하기 때문이다.

이렇게 DFS와 백트래킹을 이용하는 방법과

또, 순열(permutation)을 이용하는 방법이 있는데

이 문제의 의도는 백트래킹을 이용하는 것이므로 백트래킹을 이용해 풀어보길 추천한다.

n, m = map(int, input().split())

visited = [False] * (n + 1)
answer = []

def dfs(a):
    if a == 0:
        print(" ".join(map(str, answer)))
        return

    for i in range(1, n + 1):
        if not visited[i]:
            answer.append(i)
            visited[i] = True
            dfs(a - 1)
            answer.pop()
            visited[i] = False


dfs(m)

https://github.com/HongEunho

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

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

문제 설명

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

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

풀이 과정

이 문제를 풀기 위해선, 전위 순회(preorder)와 중위 순회(inorder), 후위 순회(postorder)가 무엇인지에 대해 알고있어야 한다.

해당 이름들은 루트를 기준으로 이름이 붙여졌는데,

루트를 가장 먼저 방문하여 루트 -> 왼쪽자식 -> 오른쪽 자식을 방문하면 전위(preorder) 순회

루트를 중간에 방문하여 왼쪽자식 -> 루트 -> 오른쪽 자식을 방문하면 중위(inorder) 순회

루트를 마지막에 방문하여 왼쪽자식 -> 오른쪽자식 -> 루트를 방문하면 후위(postorder) 순회 이다.

이를 이용해 재귀문을 돌리면 된다.

위 그림과 같은 경우에는 

• 전위 순회 : A -> B -> D -> C -> E -> F -> G
• 중위 순회 : D -> B -> A -> E -> C -> F -> G 
• 후위 순회 : D -> B -> E -> G -> F -> C -> A 으로 나타난다.

전위순회를 예로 들자면 초기 루트인 A를 가장 먼저 방문하고,

A의 왼쪽자식들을 모두 방문한 후에 오른쪽 자식들을 방문하므로 위와 같은 결과가 나온다.

이 때, A가 왼쪽 자식들을 모두 방문하기 전에 오른쪽 자식들을 방문하지 않기 위해선

즉, A의 왼쪽을 모두 방문하고 나서야 B를 방문하기 위해선

A의 왼쪽 자식먼저 깊이우선 탐색을 실행해야 할것이다.

따라서 재귀문으로 실행시켜주면 된다.

트리는 파이썬의 딕셔너리를 이용하는 방법이 있고

리스트를 이용하는 방법이 있는데,

이번 풀이는 리스트를 이용해 아스키코드를 계산해주어 각 알파벳에 맞는 칸에 트리의 원소들을 넣어주었다.

(딕셔너리를 이용한 풀이가 좀 더 간결하니 두 방법 모두 시도해보는 것을 추천한다.)

n = int(input())

graph = [[[] for _ in range(2)] for _ in range(26)]


def pre_order(root):
    print(chr(root + ord('A')), end='')
    if graph[root][0]:
        pre_order(graph[root][0][0])
    if graph[root][1]:
        pre_order(graph[root][1][0])

def in_order(root):
    if graph[root][0]:
        in_order(graph[root][0][0])
    print(chr(root + ord('A')), end='')
    if graph[root][1]:
        in_order(graph[root][1][0])

def post_order(root):
    if graph[root][0]:
        post_order(graph[root][0][0])
    if graph[root][1]:
        post_order(graph[root][1][0])
    print(chr(root + ord('A')), end='')

for i in range(n):
    a, b, c = input().split()

    if b != ".":
        graph[ord(a) - ord('A')][0].append(ord(b) - ord('A'))
    if c != ".":
        graph[ord(a) - ord('A')][1].append(ord(c) - ord('A'))


pre_order(0)
print()
in_order(0)
print()
post_order(0)

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/1012

문제 설명

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

풀이 과정

BFS로 문제를 해결하였다.

1이 인접한 칸들을 연결하여 한 구역이라고 생각하면, 구역마다 지렁이 1마리가 필요하다고 생각할 수 있다.

그래서 처음에 그래프의 각 칸을 돌다가 1인 칸을 발견하면 BFS를 수행한다.

BFS를 수행하면 1인 칸은 0으로 변경하게 되므로

한 구역의 BFS가 모두 끝나면 그 구역은 1이 모두 0으로 바뀐다.

즉, 1인 칸 하나를 발견하여 그 칸에서 BFS를 수행하면 그 구역의 1은 모두 0으로 바뀌므로

1인 칸을 발견할 때 마다 카운트 +1 을 하고 BFS를 수행하면 정답을 구할 수 있다.

( 이 부분이 아래 코드의 가장 마지막 부분이다. print(cnt) 바로 윗 부분 )

from collections import deque

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

t = int(input())

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

    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 graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
    return

for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

    for j in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1

    for a in range(n):
        for b in range(m):
            if graph[a][b] == 1:
                bfs(graph, a, b)
                cnt += 1
    print(cnt)

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/2667

문제 설명

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.

철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.

여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.

대각선상에 집이 있는 경우는 연결된 것이 아니다.

<그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다.

지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

풀이 과정

전형적인 DFS, BFS 문제로 두 가지 방법 모두 풀 수 있는 문제입니다.

풀이 ① BFS

그래프의 탐색 시작점을 모르기 때문에 전체를 돌면서 1인 지점에서 탐색을 시작합니다.

탐색 중 1인 부분은 0으로 바꿔 다시 방문하지 않도록 하고

한 번의 BFS가 끝나게 되면 더 이상 확장이 불가능 하므로 마을 하나가 탄생합니다.

이 마을안의 1의 개수들을 출력하면 되므로 다음 코드와 같이 count를 반환하면 됩니다.

from collections import deque

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


def bfs(graph, a, b):
    n = len(graph)
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0
    count = 1

    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:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
                count += 1
    return count


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

cnt = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt.append(bfs(graph, i, j))

cnt.sort()
print(len(cnt))
for i in range(len(cnt)):
    print(cnt[i])

풀이 ② DFS

그래프의 탐색 시작점을 모르기 때문에 전체를 돌면서 1인 지점에서 탐색을 시작합니다.

BFS와의 차이점은 큐 대신 재귀를 썼다는 점입니다.

그 외는 위의 BFS풀이 방식대로 똑같이 진행하시면 됩니다.

n = int(input())
graph = []
num = []

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

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


def DFS(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global count
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx, ny)
        return True
    return False


count = 0
result = 0

for i in range(n):
    for j in range(n):
        if DFS(i, j) == True:
            num.append(count)
            result += 1
            count = 0

num.sort()
print(result)
for i in range(len(num)):
    print(num[i])

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/1260

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제이다.

풀이 과정

풀이 ① - 그래프를 인접리스트로 구현

graph[a].append(b)의 의미는 a번에 b번을 연결시키는 뜻이다.

즉 1번에 2, 3, 4 가 연결되어 있으면 graph의 1번째 행에 2,3,4를 추가하게 된다.

그리고 문제에서, 번호가 작은것 부터 탐색하라고 했으므로 정렬을 해주어야 한다.

from collections import deque

n, m, v = map(int, input().split())
graph = [[]*(n+1) for _ in range(n+1)]
visited = [False]*(n+1)

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

def dfs(graph, visited, v):
    visited[v] = True
    print(v, end=' ')

    for i in range(len(graph[v])):
        if not visited[graph[v][i]]:
            dfs(graph, visited, graph[v][i])

def bfs(graph, visited, v):
    queue = deque()
    queue.append(v)
    visited[v] = False

    while queue:
        cur = queue.popleft()
        print(cur, end=' ')
        for i in range(len(graph[cur])):
            if visited[graph[cur][i]]:
                queue.append(graph[cur][i])
                visited[graph[cur][i]] = False


dfs(graph, visited, v)
print()
bfs(graph, visited, v)

풀이 ② - 그래프를 인접행렬로 구현

인접행렬은 알아서 앞에서 부터 탐색하기 때문에 정렬을 할 필요는 없다.

인접리스트에서 graph[a].append(b) 로 구현한 부분을 graph[a][b] = graph[b][a]로 구현하면 된다.

from collections import deque

n,m,v = map(int,input().split())
graph = [[0]*n for _ in range(n)]
visited = [False]*n

for i in range(m):
    a, b = map(int,input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = 1

def DFS(v):
    visited[v] = True
    print(v+1, end=' ')

    for i in range(n):
        if graph[v][i]==1 and not visited[i]:
            DFS(i)

def BFS(start):
    visited[start] = False
    queue = deque()
    queue.append(start)

    while queue:
        v = queue.popleft()
        print(v+1, end=' ')

        for i in range(n):
            if graph[v][i]==1 and visited[i]:
                queue.append(i)
                visited[i]=False

DFS(v-1)
print()
BFS(v-1)

https://github.com/HongEunho

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

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

programmers.co.kr/learn/courses/30/lessons/67259

문제 설명

문제의 설명이 위 링크에 상세하게 나와있습니다.

(0,0) 칸 부터 (N-1, N-1)칸 까지 가는데 최소한의 비용을 구하는 문제입니다.

풀이 과정

시작지점에서 오른쪽과 아래쪽의 루트 중 한가지를 선택할 수 있습니다.

그래서 오른쪽으로 가는방법과 아래쪽으로 가는 방법 둘 다 실행해서

더 작은 값을 정답으로 출력하면 됩니다.

코드 설명은 다음과 같습니다.

price는 각 칸까지의 비용을 저장하는 그래프입니다.

시작지점은 0원이므로 0으로 저장을 하고 나머지 지점은 max값으로 지정을 합니다.

다음칸 까지 이동하는데, 방향이 같으면 100원, 방향을 꺾으면 600원을 추가하여

그 추가한 금액이 저장된 금액보다 적을 경우에만 값을 갱신합니다.

처음에는 max값으로 설정되어 있어, 무조건 갱신되겠지만

갱신된 곳은 더 적은 경우에만 갱신하게 됩니다.

마지막으로, 도착 칸의 값을 리턴하면 됩니다!

from collections import deque

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


def bfs(board, dir):
    n = len(board)
    price = [[int(1e9)] * n for _ in range(n)]
    price[0][0] = 0

    queue = deque()
    queue.append((0, 0, 0, dir))  # (시작X, 시작Y, 시작Cost, 시작방향)

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

        if x == n - 1 and y == n - 1:
            continue

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

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

            if nz == z:
                nc = c + 100
            else:
                nc = c + 600

            if nc < price[nx][ny]:
                price[nx][ny] = nc
                queue.append((nx, ny, nc, i))

    return price[-1][-1]


def solution(board):
    answer = min(bfs(board, 0), bfs(board, 2))
    return answer

두 번째 풀이는 bfs를 한 번만 실행하여 값을 구하는 방법입니다.

시작지점에서는 오른쪽 아래쪽 둘 다 움직일 수 있으므로

예외사항으로, 5라는 방향을 주어 두 방향 모두 100원을 추가하도록 합니다.

(단, 여기서 price칸 값을 갱신할 때 " < " 가 아닌 " <= " 를 해주어야 합니다. 그래야 같은 칸에서 두 방향으로 온 값이 겹쳤을 때 값이 같게되면, 멈추지 않고 계속 진행하게 됩니다. )

from collections import deque

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

def bfs(board):
    n = len(board)
    price = [[int(1e9)] * n for _ in range(n)]
    price[0][0] = 0

    queue = deque()
    queue.append((0, 0, 0, 5))  # (시작X, 시작Y, 시작Cost, 시작방향)

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

        if x == n - 1 and y == n - 1:
            continue

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

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if board[nx][ny] == 1:
                continue
            
            if z==5:
                nc = c + 100

            elif nz == z:
                nc = c + 100
                
            else:
                nc = c + 600

            if nc <= price[nx][ny]:
                price[nx][ny] = nc
                queue.append((nx, ny, nc, i))

    return price[-1][-1]


def solution(board):
    n = len(board)
    answer = bfs(board)
    return answer

https://github.com/HongEunho

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

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

www.acmicpc.net/problem/15658

문제 설명

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

풀이 과정

DFS의 백트래킹을 이용해서 풀어도 되고, 아래의 코드처럼 변수로 변하는 변수를 넘겨주어도 됩니다.

핵심은 주어진 숫자와 연산자로 조합할 수 있는 모든 경우의 수를 따져야 합니다.

백트래킹을 이용한 코드는

https://hongcoding.tistory.com/119 에 있습니다!

연산자 끼워넣기 1, 2 같은 방식으로 풀면 되므로 해당코드를 참고하셔도 좋습니다.

n = int(input())
num = list(map(int, input().split()))
plus, minus, mul, div = map(int, input().split())

mymax = int(-1e9)
mymin = int(1e9)

def dfs(index, result, plus, minus, mul, div):
    global mymax, mymin
    if index == n:
        mymax = max(mymax, result)
        mymin = min(mymin, result)
        return
    if plus > 0 :
        dfs(index + 1, result + num[index], plus-1, minus, mul, div)
    if minus > 0 :
        dfs(index + 1, result - num[index], plus, minus-1, mul, div)
    if mul > 0:
        dfs(index + 1, result * num[index], plus, minus, mul-1, div)
    if div > 0 :
        dfs(index + 1, int(result / num[index]), plus, minus, mul, div-1)


dfs(1, num[0], plus, minus, mul, div)
print(mymax)
print(mymin)

https://github.com/HongEunho

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

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