태야

<내 코드>

N, M = map(int, input().split())
maze = [list(input()) for _ in range(N)]  # List[str]
# 방문 경로
done = [[0]*M for _ in range(N)]

# 좌,우,상,하 탐색을 위한 설정
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# BFS 그래프 탐색
def bfs(x, y):

    done[0][0] = 1  # 시작점
    queue = [(0, 0)]  # 큐 사용

    while queue:
        now = queue.pop(0)
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]

            if (0 <= nx < N) and (0 <= ny < M):
                if done[nx][ny] == 0 and maze[nx][ny] == '1':
                    done[nx][ny] = done[now[0]][now[1]] + 1
                    queue.append((nx, ny))
    return done[-1][-1]

print(bfs(0, 0))

처음 풀어보는 BFS 문제였는데.. 이해하는데 꽤나 어려웠다. 계속 반복적으로 생각하고 익혀야겠다.

1. 방문한 경로를 저장하기 위해 done 배열을 만든다.

2. 길을 찾아나갈 노드를 queue에 담아준다.

3. 좌표가 경로를 벗어나지 않는다면 '방문 여부 확인', '길이 맞는지' 확인한다.

4. 상,하,좌,우로 확인해 연결된 좌표를 확인한다.

5. 조건에 맞다면 방문 여부 수정 후, 큐에 넣어 다음 차례에 추가한다.

6. 방문여부 수정 때, 몇 번째 방문인지 현재 좌표의 방문 값에 +1을 더해준다.

7. done 배열의 가장 마지막 요소를 출력하면 몇 번째만에 도착인지 알 수 있다.

<내 코드>

def dfs(v):
    done.append(v)  # 방문한 노드 추가
    # print(done)
    # 해당 행(노드) 탐색(1행 ~ n행)
    for i in range(1, n+1):
        if (i not in done) and (matrix[v][i] == 1):
            dfs(i)

    return done


def bfs(start):
    queue = [start]
    done = [start]

    while queue:
        v = queue.pop(0)
        for i in range(1, n+1):
            if (i not in done) and (matrix[v][i] == 1):
                queue.append(i)
                done.append(i)

    return done


n, m, v = map(int, input().split())
done = []
matrix = [[0]*(n + 1) for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())
    matrix[x][y] = 1
    matrix[y][x] = 1

print(*dfs(v))
print(*bfs(v))

그래프를 표현하기 위해 여기서는 '인접 행렬' 방식으로 구현했다. DFS(깊이 우선 탐색)은 주로 스택과 재귀를 통해 구현하고 BFS(너비 우선 탐색)은 큐로 구현을 많이 한다.

<내 코드>

N, M = map(int, input().split())
cnt_block = 1


if N == 1:
    cnt_block = 1
elif N == 2:
    if (M >= 7):
        cnt_block = 4
    else:
        cnt_block = (M+1) // 2

elif N >= 3:
    if(M >= 7):
        cnt_block = (M - 2)
    elif(M >= 4):
        cnt_block = 4
    else:
        cnt_block = M

print(cnt_block)

경우 별로 따져줘야 할 조건이 까다로웠다... 문제 자체는 어렵지 않으나 경우 별로 조건을 잘 못하면 머리가 복잡해지는 문제다..

<내 코드>

N = int(input())
H = list(map(int, input().split()))
result = [0] * N

for i in range(N):
    cnt_zero = 0

    for j in range(N):
        if cnt_zero == H[i] and result[j] == 0:
            result[j] = i + 1  # 수 1 ~ N
            break
        elif(result[j] == 0):
            cnt_zero += 1

print(*result)

입력 값으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. 그리고 줄을 선 순서대로 키를 출력하면 된다. 

# result
# 입력: [2, 1, 1, 0]
[0, 0, 1, 0]
[0, 2, 1, 0]
[0, 2, 1, 3]
[4, 2, 1, 3]

차례대로 각자 왼쪽에 큰 사람이 몇 명인지를 0의 개수로 판단해서 자리에 넣어준다. 예를 들어 왼쪽에 2명이 있다 하면 결과값 배열에 [0, 0, 현재,...] 즉, 자신보다 큰 2명의 자리를 비워두고 자리에 들어가면 된다. 그렇게 되면 다음 사람은 앞전보다 큰 사람이기 때문에 앞사람 위치는 무시하고 자신보다 큰 사람 수와 0의 수만 같으면 그 자리에 들어가면 된다.