본문 바로가기
취업과 기본기 튼튼/코딩 테스트 노트

[BOJ] 16236. 아기 상어

흠시 2019. 4. 10. 00:06

문제

아기 상어 (https://www.acmicpc.net/problem/16236)

풀이

1. 초기 접근

  • 문제조건 해석
    • 일단 문제조건이 뭔가 되게 복잡해서, 잘 읽어야한다.
      • 삼성 문제 특징이다.
    • 이동할 수 있는 각 경우는 상하좌우 4가지 방향이 있고, 한 번에 1칸 이동할 수 있다.
      우리는 최종 이동까지의 시간을 구해야 한다.
      • BFS 문제다.
  • 알고리즘
    • 일단 진짜로 문제를 잘 하나하나 읽고, 예제로 주어진 케이스들을 손으로 풀면서, 내가 잘 이해했는지 확인해보자.
    • 그럼 다음과 같이 차례대로 생각해볼 수 있다.
  1. 먼저 자기보다 크기가 작은 물고기들을 찾는다.
  2. 그 중, 가장 가까운 애들부터 먹으러 가서 먹는다.
  3. 지금까지 먹은 횟수가 현재 내 크기만큼 되는지 체크한다.
    • 만약 내 크기만큼 된다면, 내 크기를 한 단계 업그레이드 시키고, 먹은 횟수를 초기화해야 한다.
  4. 먹은 이후, 다시 현재 위치를 기준으로, 1을 1~3을 반복한다.

  • 좀 더 구체화.

    • 위 시나리오에서, 1과 2에 BFS를 적용시킬 수 있는데,
      일단, 현재 위치기준으로 가장 가까운 물고기들을 탐색하는데에 BFS 를 이용한다.

    • 이렇게 하나씩 방문하는데, 방문한 위치가 물고기고, 해당 물고기가 지금 내 크기보다 작다면, 먹는다.

    • 먹고 나서는, 다시 현재 위치기준으로 주위를 BFS를 탐색한다.
      이 때, 먹고 난 뒤, BFS queue 를 싹 비워줘야 한다. 그래야 현재 위치 기준으로 새로운 탐색을 하는 것이니깐.

    • 또한 문제조건에서 핵심이 되는건 아래 구문이다.

      거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽 에 있는 물고기를 먹는다.

    • 일반적으로 BFS에서는, BFS queue 에 다음 방문할 좌표를 계속해서 넣어주고, 다음 스텝에서 queue에 있는걸 하나씩 빼오는 구조다.
      그리고 위 알고리즘 대로라면, 이렇게해서 queue에서 뺀 좌표가 현재 내 자신의 크기보다 작을경우 그냥 먹어버린다. 근데 위같이 하면, 저 핵심이 되는 조건, 즉 가장 위에 있는 물고기가 우선시 되고, 그 다음 왼쪽에 있는 물고기가 우선시 되지 않는다.

    • 이를 해결하려면, 다음 스텝에서 queue 에서 하나씩 빼오기 전에, queue 에 있는 아이템들을 한번 싹 정렬해줘야 한다. 그러면, 다음 이동 좌표에서 가장 위에있는 행, 그리고 가장 왼쪽에 있는 열이 먼저 뽑히게 된다.

    • 지금까지 주저리 주저리 쓴걸 코딩해보자.

  • 코드

from collections import deque

dxs = [-1, 0, 0, 1]
dys = [0, -1, 1, 0]

# 현재 판에 shark의 크기보다 작은 게 없는지 조사한다.
# 만약 없다면, 더 이상 진행할 필요가 없으므로 False를 리턴하고, 있으면 True를 반환한다.
def check_board(shark):
    for i in range(n):
        for j in range(n):
            if board[i][j] != 0 and board[i][j] < shark:
                return True
    return False

def bfs(x, y):
    q, visited = deque([(x, y)]), set([(x, y)])
    time = 0
    shark = 2  # 현재 아기 상어의 크기다.
    eat = 0    # 현재 크기에서, 지금까지 먹은 물고기 수다.
    eat_flag = False  # 현재 상태에서 물고기를 먹은 경우, 
                      # for _ in range(size) 구문을 진행하지 않기 위한 플래그다.

    while q:
        size = len(q)

        # 위, 그리고 왼쪽을 더 우선시해서 가야하기 때문에, BFS queue를 소팅해준다.
        q = deque(sorted(q))
        for _ in range(size):
            x, y = q.popleft()

            # 현재 위치에 아기 상어보다 작은 물고기가 있어서, 이를 먹은 경우.
            if board[x][y] != 0 and board[x][y] < shark:
                board[x][y] = 0
                eat += 1

                # 아기 상어의 크기 만큼 먹었다면, 아기 상어의 크기를 +1 해줘야한다.
                if eat == shark:
                    shark += 1
                    eat = 0               

                # 먹고 난 뒤, 현재 판에 더 먹을게 있는지 확인하고 없으면 현재 스텝을 반환한다.
                if not check_board(shark):
                    return time

                # 먹고 난 뒤, 현재 위치를 기준으로 다시 근처를 탐색해야 하기 때문에,
                # BFS queue 와 visited 를 초기화 해준다.
                q, visited = deque(), set([(x, y)])
                eat_flag = True

            for dx, dy in zip(dxs, dys):
                nx, ny = x + dx, y + dy
                if nx >= 0 and nx < n and ny >= 0 and ny < n and (nx, ny) not in visited:
                    if board[nx][ny] <= shark:
                        q.append((nx, ny))
                        visited.add((nx, ny))

            # 현재 위치에서 먹었다면, 더 이상 위 반복문을 돌 필요가 없다.
            if eat_flag:
                eat_flag = False
                break

        time += 1
    return time

n = int(input())
board = [list(map(int , input().split())) for _ in range(n)]

# 1. 초기 상어(자신)의 위치를 파악하고, 해당 자리는 판에서 비워둔다.
s_x, s_y = None, None
for i in range(n):
    for j in range(n):
        if board[i][j] == 9:
            s_x, s_y = i, j
            board[i][j] = 0

# 2. 판에 더 먹을 수 있는 물고기가 있는지 판단하고, 있을 경우 BFS를 진행한다.
if check_board(2):
    print(bfs(s_x, s_y))
else:
    print(0)

2. 오류

위 코드를 제출하면 오답처리가 된다. 이유가 무엇일까????

질문 게시판을 찾던 중, 다음과 같은 테스트 케이스를 발견했다.

#input
3
9 2 2
2 2 3
1 3 1

#output
2

위 코드를 돌리면, 2가 안나온다.

위 테스트 케이스의 정답이 2인 이유는, 아기상어가 (2,0) 위치에 있는 물고기를 먹고 난 뒤, 더 이상 먹을 수 있는 물고기가 없기 때문이다.
(2,2) 에 위치한 물고기도 있지만, 주위에 큰 물고기들 때문에 갈 수가 없다.

다시 우리의 코드를 보면, def check_board(shark) 에서 판 전체를 모두 탐색하여, 현재 아기 상어의 크기보다 작은 물고기의 유무를 판단하여, 더 먹을 수 있는지 없는지를 확인해준다. 이제 "유무"가 아니라, "도달할 수 있는지 없는지" 의 기준으로 다시 확인해봐야 한다.

"도달할 수 있는지 없는지"는 사실 BFS를 하다보면 자연스레 알게된다. 도달할 수 없으면 해당 좌표로 BFS가 가지 못하고, visited 에 모든 도달할 수 있는 다른 좌표들이 모두 쌓여 자연스레 끝나게 될 것이다.

따라서, 우리는 물고기를 먹은 경우, 그 때의 시간만 저장해두면 된다. def check_board(shark) 는 더 이상 필요없다.

수정한 코드

from collections import deque

dxs = [-1, 0, 0, 1]
dys = [0, -1, 1, 0]

def bfs(x, y):
    q, visited = deque([(x, y)]), set([(x, y)])
    time = 0
    shark = 2  # 현재 아기 상어의 크기다.
    eat = 0    # 현재 크기에서, 지금까지 먹은 물고기 수다.
    eat_flag = False  # 현재 상태에서 물고기를 먹은 경우, 
                      # for _ in range(size) 구문을 진행하지 않기 위한 플래그다.
    answer = 0

    while q:
        size = len(q)

        # 위, 그리고 왼쪽을 더 우선시해서 가야하기 때문에, BFS queue를 소팅해준다.
        q = deque(sorted(q))
        for _ in range(size):
            x, y = q.popleft()

            # 현재 위치에 아기 상어보다 작은 물고기가 있어서, 이를 먹은 경우.
            if board[x][y] != 0 and board[x][y] < shark:
                board[x][y] = 0
                eat += 1

                # 아기 상어의 크기 만큼 먹었다면, 아기 상어의 크기를 +1 해줘야한다.
                if eat == shark:
                    shark += 1
                    eat = 0               

                # 먹고 난 뒤, 현재 위치를 기준으로 다시 근처를 탐색해야 하기 때문에,
                # BFS queue 와 visited 를 초기화 해준다.
                q, visited = deque(), set([(x, y)])
                eat_flag = True

                # 먹었을 때의 시간을 저장해둔다.
                answer = time

            for dx, dy in zip(dxs, dys):
                nx, ny = x + dx, y + dy
                if nx >= 0 and nx < n and ny >= 0 and ny < n and (nx, ny) not in visited:
                    if board[nx][ny] <= shark:
                        q.append((nx, ny))
                        visited.add((nx, ny))

            # 현재 위치에서 먹었다면, 더 이상 위 반복문을 돌 필요가 없다.
            if eat_flag:
                eat_flag = False
                break

        time += 1
    return answer

n = int(input())
board = [list(map(int , input().split())) for _ in range(n)]

# 1. 초기 상어(자신)의 위치를 파악하고, 해당 자리는 판에서 비워둔다.
s_x, s_y = None, None
for i in range(n):
    for j in range(n):
        if board[i][j] == 9:
            s_x, s_y = i, j
            board[i][j] = 0

# 2. 시작점에서 BFS 진행
print(bfs(s_x, s_y))

여담

기초 BFS 문제에서 조금씩 꼬아내는 형태의 문제라고 생각한다.
기본적인 BFS 틀 이지만, 이동하는 형태라든가, 고려해야하는 조건들이 더 붙는다.

큰 틀의 알고리즘은 어렵지않게 생각할 수 있지만, 위와 같이 생각치 못한 테스트 케이스나, 예외 케이스에 좀 더 신경을 써야겠다. 근데 그럴려면, 많이 푸는게 역시 정답인 듯 하다.

저작자표시

'취업과 기본기 튼튼 > 코딩 테스트 노트' 카테고리의 다른 글

[BOJ] 16234. 인구 이동  (0) 2019.04.10
[BOJ] 16235. 나무 재테크  (2) 2019.04.10
[BOJ] 13460. 구슬 탈출 2  (0) 2019.04.09
[BOJ] 1964. 소수 경로  (0) 2019.04.08
[BOJ] 2636. 치즈  (0) 2019.04.08

'취업과 기본기 튼튼/코딩 테스트 노트' Related Articles

티스토리툴바