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

문제 풀이

전형적으로 그래프 탐색 이론인 BFS(너비 우선 탐색)를 이용하면 쉽게 풀리는 문제다.

다만 보편적인 그래프 탐색은 2차원 배열에서 인덱스 접근을 통해 4방 혹은 8방 탐색을 하며 가장 가까운 Target Node를 찾지만 이번 문제는 1번부터 100번까지 각 노드를 번호로 구분할 수 있는 점, 1부터 6까지 적혀있는 주사위를 던져서 옮긴다는 점에 착안하여 1차원 배열에서 6가지 방법을 고려하면 된다는 것을 깨달아야 한다.

이점 외에는 딱히 조심해야 할 부분이 없으므로 바로 코드를 통해 설명하도록 하겠다.

from collections import deque
edge_info=[0 for i in range(101)]
n,m=map(int,input().split())
visited=[0 for i in range(100)]
queue=deque()
for i in range(n+m):
    temp=list(map(int,input().split()))
    edge_info[temp[0]]=temp[1]

             #curr,cnt
queue.append([1,0])
while len(queue)>0:
    curr,cnt=queue.popleft()
    if curr==100:
        print(cnt)
        break
    elif curr>=94:
        print(cnt+1)
        break
    else:
        for i in range(1,7):
            if edge_info[curr+i]==0 and visited[curr+i]==0:
                visited[curr+i]=1
                queue.append([curr+i,cnt+1])
            else:
                if visited[curr+i]==0:
                    visited[curr+i]=1
                    visited[edge_info[curr+i]]=1
                    queue.append([edge_info[curr+i],cnt+1])

1번째 줄은 deque를 사용하기 위해 모듈을 Import 하였다.

물론 이번 문제는 최대 칸이 100개 밖에 없기 때문에 애초에 사이즈가 작아서 시간 복잡도를 줄이기 위해 굳이 deque를 사용할 필요는 없었지만 막상 필요한 상황에서 참고 문서 없이 Import 하려면 까먹기 때문에 잊지 않기 위해서라도 deque를 사용하였다.

만약 deque가 무엇인지 모르는 사람들은 아래 포스팅을 통해 학습하면 될 것이다.

https://khsung0.tistory.com/14

2번째 줄부터 5번째 줄까지는 간선 정보와 방문 체크, 큐 등을 사용하기 위한 초기화 작업이다.

6번째 줄은 반복문을 통해 간선 정보를 저장하였고 11번째 줄은 1번 칸부터 시작해서 BFS를 진행하기 위해 deque에 초기화했다.

12번째 줄부터는 BFS를 구현한 코드이다.

문제에 주어진대로만 구현하면 되기 때문에 딱히 설명할 부분은 없지만 필자는 조금이라도 시간 복잡도 상으로 효율적인 코드를 구현하기 위해 100일 때는 현재 카운트 출력, 94 이상일 때는 주사위를 한 번만 더 돌리면 100이 나오므로 카운트+1 출력, 그 외의 경우에만 다시 deque에 넣도록 구현하였다.

이렇게 구현하면 매번 deque에 넣을 때도 100을 초과하는지 체크하지 않아도 되기 때문이다.

문제는 10X10의 2차원 그래프인 것처럼 나왔지만 1차원 배열로 변환하여 생각하는 게 필요한 문제였다.

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

문제 풀이

어렸을 때 많이 했던 뿌요뿌요(PuyoPuyo) 게임의 연쇄작용을 구현하는 문제이다.

테트리스와 비슷하지만 뿌요뿌요는 같은 색의 슬라임들이 4개 이상 연결되어있으면 터지고 빈 공간을 채운다는 점이 조금 다르다.

따라서 만약 테트리스였다면 행을 기준으로 탐색을 했겠지만 뿌요뿌요는 전체 탐색을 하면서 빈 공간이 아닐 때는 4개 이상 연결되었는지 BFS를 통해 체크하며 4개 이상인 모든 부분들을 빈 공간으로 치환하고 다시 바닥으로 정렬하는 과정을 반복해야 한다.

이때 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터지고 한 번의 연쇄가 추가된다고 하니 연쇄를 추가하는 부분을 정렬하는 과정에 위치시키면 적절할 것이다.

사실 12X6 크기의 행렬이라 상당히 크기가 작아 시간이나 공간에 대한 효율성을 따질 필요성까진 없지만 구현하는 과정에서 다소 헷갈리거나 복잡한 부분이 있었기에 문제를 세분화하여 주석을 통해 구현해야 할 기능들을 구분해놓고 구현하는 것이 도움 될 것 같다.

코드가 짧은 편은 아니라서 한눈에 들어오긴 힘들겠지만 한 줄씩 따라가다 보면 이해할 수 있을 것이다.

graph=[]
dir=[[-1,0],[1,0],[0,-1],[0,1]]
queue=[]
for i in range(12):
    graph.append(list(input()))
res=0

while True:
    check=True    #터졌는지 체크하는 변수
    visited=[[0 for i in range(6)]for j in range(12)]
    changed_col=[]
    del_queue=[]
    for i in range(12):
        for j in range(6):
            #뿌요가 존재하는 칸인 경우
            if graph[i][j]!="." and visited[i][j]==0:
                curr_char=graph[i][j]    #현재 뿌요 저장
                temp_cnt=0
                queue.append([i,j])
                visited[i][j]=1
                
                #현재뿌요와 연결되어있는 뿌요 탐색
                while len(queue)>0:
                    curr=queue.pop(0)
                    temp_cnt+=1
                    for k in range(len(dir)):
                        dy=dir[k][0]+curr[0]
                        dx=dir[k][1]+curr[1]
                        if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char and visited[dy][dx]==0:
                            queue.append([dy,dx])
                            visited[dy][dx]=1

                #연결된 뿌요가 4개 이상일 경우
                if temp_cnt>=4:
                    check=False
                    changed_col.append(j)
                    del_queue.append([i,j])
                    while len(del_queue)>0:
                        temp=del_queue.pop(0)
                        graph[i][j]="."
                        for k in range(len(dir)):
                            dy=dir[k][0]+temp[0]
                            dx=dir[k][1]+temp[1]
                            if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char:
                                del_queue.append([dy,dx])
                                graph[dy][dx]="."
                                if dx not in changed_col:
                                    changed_col.append(dx)

    if check:
        break
    else:
        res+=1
        #빈칸없게 위에 있는 뿌요들을 정렬
        for i in range(len(changed_col)):
            for j in range(10,-1,-1):
                if graph[j][changed_col[i]]!=".":
                    curr=j
                    while curr<=10 and graph[curr+1][changed_col[i]]==".":
                        graph[curr+1][changed_col[i]],graph[curr][changed_col[i]]=graph[curr][changed_col[i]],graph[curr+1][changed_col[i]]
                        curr+=1

print(res)

6번째 줄까지는 그래프를 입력받고 방향 리스트, 사용할 큐 초기화, 결과 변수를 선언했다.

8번째 줄의 while문은 더 이상 터진 뿌요들이 없을 때까지 터뜨리고 빈칸을 정렬하는 과정을 반복하는 부분이다.

check변수를 통해 터진 뿌요가 없을 경우 반복문을 탈출하고 매번 방문했는지 체크하는 visited 리스트를 초기화하도록 구현하였다.

13번째 줄부터는 전체 리스트를 반복하면서 뿌요가 존재할 경우 현재 뿌요를 저장하고 근접한 동일 뿌요들의 개수를 세서 4개 이상이라면 해당하는 뿌요들을 빈칸으로 초기화하였다.

이때 뿌요는 5종류가 있지만 변수에 현재 위치한 뿌요를 저장함으로써 종류에 대한 고려를 하지 않도록 했고 47번째 줄의 changed_col은 삭제된 뿌요가 존재하는 열을 추가하여 이후에 뿌요들을 정렬할 때 불필요한 탐색을 줄이는 방식으로 구현하였다.

53번째 줄에서 res+=1을 통해 카운트를 증가시키는데 문제에서 터질 수 있는 뿌요가 여러 그룹이라면 동시에 터지며 한 번의 연쇄가 추가되므로 다 터지고 난 뒤에 추가하도록 증가시키는 위치를 주의해야 한다.

터진 뿌요가 없다면 50번째 줄에서 반복문을 탈출하겠지만 터진 뿌요가 존재한다면 빈칸보다 위에 뿌요가 존재하지 않도록 정렬시킨 후 다시 반복문으로 돌아가면 된다.

그래프의 행을 기준으로 리스트 시작은 위, 끝은 바닥을 뜻하므로 끝부터 시작까지 역으로 오면서 뿌요를 최대한 리스트의 끝까지 정렬하는 것에 주의해야 한다.

해당 반복문이 끝나면 결과 변수인 res를 출력하면 끝이다.

그래프의 크기도 작고 특별한 알고리즘도 없이 흔한 그래프 이론으로 푸는 구현 문제였지만 구현 과정이 다소 길어지다 보니 충분히 헷갈릴 수도 있는 문제였다.

따라서 구현해야 하는 부분과 과정을 간략하게 주석으로 써놓고 차근차근 작성해 나가는 것이 실수를 방지하기 위해 중요한 것 같다.

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

문제 풀이

전형적으로 시작 노드에서 도착 노드까지 장애물을 피해 도착하는 최단 거리를 출력하는 문제이다.

다만 다소 어렵게 느껴질 수 있는 부분은 기존의 그래프 탐색은 방문 가능한 노드인지(장애물이 아닌지), 방문한 노드인지를 체크하고 탐색하지만, 이 문제에선 최대 한 개의 벽을 부수고 이동할 수 있다는 개념이다.

아마 정답 비율이 낮은 이유(약 23%)는 이 개념 때문이지 않을까 추측해본다.

이 문제에서는 살짝 다르게 생각하는 방법이 필요하다.

물론 문제대로 매번 현재 상태가 벽을 부수고 이동한 상태인지 아닌지 기록할 수도 있겠지만 3차원 리스트로 생각하면 좀 더 이해하기 쉬울 것이다.

즉, 기존의 2차원 리스트를 2개 갖는 3차원 리스트로 생각하고 벽을 부수지 않은 상태라면 0번째 인덱스의 2차원 리스트, 벽을 부순 상태라면 1번째 인덱스의 2차원 리스트로 생각하면 된다.

벽을 부수는 것을 한 층 올라간다고 생각하면 이해가 쉬울 것이다.

이렇게 개념만 잡고 간다면 나머지는 기존의 2차원 리스트에서 최단 거리를 찾는 알고리즘과 같기 때문에 어렵지 않게 구현할 수 있을 것이다.

전체 코드를 따라가면서 이해하면 도움 될 것이다.

import sys
from collections import deque

#위,오른,아래,왼
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n,m=map(int,input().split())
graph=[]
res=-1
queue=deque()
for i in range(n):
    graph.append(list(map(int,list(sys.stdin.readline().rstrip()))))
visited=[[[0 for i in range(m)] for j in range(n)]for k in range(2)]

       #벽 부수기 전,시작위치,거리
queue.append([0,0,0,1])
visited[0][0][0]=1
while len(queue)>0:
    temp_list=queue.popleft()
    for i in range(4):
        x=temp_list[1]+dx[i]
        y=temp_list[2]+dy[i]
        if 0<=x<n and 0<=y<m:
            if x==n-1 and y==m-1:
                res=temp_list[3]+1
                break
            elif graph[x][y]==0 and visited[temp_list[0]][x][y]==0:
                visited[temp_list[0]][x][y]=1
                queue.append([temp_list[0],x,y,temp_list[3]+1])
            elif graph[x][y]==1:
                if temp_list[0]==0 and visited[0][x][y]==0:
                    visited[1][x][y]=1
                    queue.append([temp_list[0]+1,x,y,temp_list[3]+1])

    if res!=-1:
        break
if n==1 and m==1:
    print(1)
else:
    print(res)

먼저 최대 1000000개의 노드가 가능한 그래프이고 3차원 리스트로 생각하므로 최대 2000000개가 가능하기에 최대한 시간을 줄일 필요성이 있었다.

따라서 sys 모듈을 이용하여 입력 시간을 줄였고 시작과 끝부분에서 데이터 삽입 삭제가 가능한 deque 모듈을 사용하여 BFS에서 최대한 시간을 줄이려고 노력했다.

그냥 List에서 BFS를 위해 pop(0)을 한다면 매번 O(n)의 시간 복잡도가 걸리기 때문이다.

5, 6번째 줄에선 한 노드를 기준으로 0번째 인덱스부터 차례대로 위 노드, 오른쪽 노드, 아래 노드, 왼쪽 노드로 가능한 방향을 저장한 리스트이다.

10번째 줄은 BFS 탐색을 위해 데크로 선언하였다.

11번째 줄에선 그래프로 저장하며 13번째 줄의 visited 리스트는 각 각 방문한 노드인지 체크하는 리스트인데 중요한 것은 3차원 리스트로 선언한 것이다.

최대 한 번 벽을 부수고 이동할 수 있기 때문에 2개의 2차원 리스트로 선언했고 만약 2번 3번 벽을 부수고 이동한다면 각 층을 올라간다고 생각하여 3개, 4개의 2차원 리스트로 선언하면 된다.

16번째 줄에서 데크에 넣은 리스트는 벽을 부수기 전, 시작 위치, 거리이다.

그러고 나서 18번째 줄에서 BFS를 실행하면 된다.

19번째 줄의 popleft()는 O(1)의 시간 복잡도가 걸리고 24번째 줄에선 도착하면 res를 갱신한 뒤 BFS를 탈출한다.

27번째 줄은 방문 가능한 노드일 경우 데크에 넣는 코드고 30번째 줄은 벽이 있을 때 부수고 온 상태가 아니라면 벽을 부수고(층을 이동하여) 노드를 데크에 넣어준다.

마지막으로 res를 출력하면 통과할 수 있다.

알고리즘 구현 자체는 다른 그래프 탐색과 비슷한 수준이지만 벽을 부수고 이동할 수 있다는 조건 때문에 어렵게 다가왔다.

주어진 조건을 이해와 구현이 쉬운 방법으로 변환하는 게 핵심 포인트이며 이처럼 다차원 리스트로 변환하여 생각하는 방법은 은근히 나오니 꼭 익숙해지는 게 좋을 것 같다.

비슷하게 다차원 리스트를 이용하는 문제를 추천하며 마무리 짓도록 하겠다.

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

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

문제 풀이

문제에서도 한눈에 알 수 있듯이 그래프 탐색을 하는 문제다.

문제를 간략하게 다시 설명하자면 0은 비어있는 땅, 1은 배추가 있는 땅이고 각 케이스마다 배추가 이어져있는 구역을 세서 출력하면 된다.

그래프를 탐색하는 방법은 스택을 쓰는지, 큐를 쓰는지에 따라 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)으로 나뉘는데 둘 다 시간 복잡도는 비슷하므로 편한 방식으로 구현하면 된다.

필자는 최단 거리를 찾을 때 BFS가 유리하므로 보통 BFS로 구현한다.

바로 전체 코드를 확인해 보자.

testcase=int(input())
dir=[[-1,0],[0,1],[1,0],[0,-1]]
for i in range(testcase):
    queue=[]
    res=0
    M,N,K=map(int,input().split())
    graph=[[0 for j in range(M)]for k in range(N)]
    for j in range(K):
        tempm,tempn=map(int,input().split())
        graph[tempn][tempm]=1
    for j in range(N):
        for k in range(M):
            if graph[j][k]==1:
                res+=1
                queue.append([j,k])
                graph[j][k]=0
                while len(queue)>0:
                    tempn,tempm=queue.pop(0)
                    for a in range(len(dir)):
                        dx=tempn+dir[a][0]
                        dy=tempm+dir[a][1]
                        if 0<=dx<N and 0<=dy<M and graph[dx][dy]==1:
                            graph[dx][dy]=0
                            queue.append([dx,dy])
    print(res)

1번째 줄은 테스트 케이스만큼 반복하기 위한 변수이고 2번째 줄은 각 노드에서 탐색 방향(위, 오른쪽, 아래, 왼쪽)을 묶어놓은 리스트이다.

이렇게 방향을 리스트로 묶으면 4가지 방향을 탐색할 때 반복문으로 해결할 수 있다는 장점이 있기에 꼭 잊지 말길 바란다.

대부분은 4가지 방향이지만 가끔 대각선도 고려하는 8가지 방향 문제도 있는데 단순하게 방향을 고려해서 8개의 리스트를 넣으면 된다.

4번째 줄의 queue는 큐를 사용함으로써 BFS 방식을 쓰기 위해 선언한 리스트이다.

가끔 리스트를 큐 방식으로 쓸 때 시간 초과가 나는 경우가 있는데 이는 pop() 함수에서 마지막 원소부터 탐색하기 때문에 첫 번째 원소를 제거하기 위해서는 O(n)의 시간 복잡도가 걸리기 때문이다.

그럴 경우엔 deque 모듈을 사용하면 O(1)로 첫 번째 원소에 삽입하고 삭제할 수 있다.

8번째 줄은 배추의 위치를 갱신하는 반복문이고 11번째 줄부터는 그래프를 전체 탐색하면서 배추 구역을 카운트하는 반복문이다.

13번째 줄은 배추가 있을 경우 카운트를 하고 인접한 배추 구역을 0으로 바꾸는 작업이다.

보통 원본 그래프를 변경하지 않기 위해 visited로 그래프와 똑같은 크기의 리스트를 선언하고 방문한 노드인지 아닌지 체크하여 중복된 방문을 방지하는데 해당 문제에서는 단지 배추 구역만 세면 되므로 원본 리스트를 변경해도 상관없어서 아예 0으로 바꿨다.

또한 20, 21번째 줄에서 탐색할 노드의 위치를 계산하여 따로 변수에 저장하는 이유는 미리 값을 저장해놔야 그래프 크기 안인지 배추가 있는 노드인지 체크할 때 불필요한 연산 횟수를 줄일 수 있기 때문에 값을 저장하는 것을 추천한다.

탐색 방향을 고려할 필요도 없고 단지 구역만 세면 되기 때문에 그래프 문제 중에서도 꽤 쉬운 편에 속한다고 생각한다.

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

문제 풀이

2차원 그래프에서도 상당히 쉬운 편에 속하는 문제였다.

그림의 가로길이는 짝수이며 접었을 때 물감이 겹치는 부분도 없다고 하니 그냥 구간을 절반으로 나눠 물감이 있으면 반대편에도 추가하는 방식으로 풀면 되는 브론즈다운 문제였다.

상당히 쉬우니 바로 전체 코드로 넘어가겠다.

n,m=map(int,input().split())
graph=[]
for i in range(n):
    temp=list(input())
    for j in range(m//2):
        if temp[j]!='.':
            temp[m-j-1]=temp[j]
        elif temp[m-j-1]!='.':
            temp[j]=temp[m-j-1]
    graph.append(temp)
    
for i in range(len(graph)):
    for j in range(len(graph[i])):
        print(graph[i][j],end="")
    print()

각 줄을 입력받으면서 바로 물감을 갱신한 뒤 그래프에 추가하여 출력하는 방식으로 구현했다.

5번째 줄이 물감을 갱신하는 반복문이며 구간을 절반으로 나눠 6번째 줄은 첫 문자부터 절반 부분까지, 8번째 줄은 뒷 문자부터 절반 부분까지 물감이 있으면 반대편에 추가하고 완료되면 그래프에 추가했다.

그리고 완전 탐색을 통해 그래프 출력만 하면 되는 쉬운 문제였다.

만약에 인덱싱 부분이 헷갈린다면 작은 숫자를 몇 개 대입해보면 쉽게 해결할 수 있을 것이다.