문제 소개 🧐

입력 📝

  • 첫째 줄에 캠퍼스의 크기 N과 M이 주어집니다. (1 ≤ N, M ≤ 600)
  • 둘째 줄부터 N개의 줄에 걸쳐 캠퍼스의 정보가 주어집니다.
    • O: 빈 공간
    • X: 벽
    • I: 도연이 (항상 한 번만 주어짐)
    • P: 사람

출력 📤

  • 도연이가 캠퍼스에서 만날 수 있는 사람의 수를 출력합니다.
  • 만약 아무도 만나지 못했다면 ‘TT’를 출력합니다.

나의 아이디어와 코드 👨‍💻

Idea 1️⃣

처음에는 간단하게 BFS를 이용해서 풀 수 있겠다고 생각했다

  1. 시작 위치부터 갈 수 있는 모든 곳을 탐색하고, 방문한 좌표를 리스트에 저장하고
  2. 저장된 좌표 리스트를 전부 돌면서 ‘P’가 몇 개인지 세어보려고 했다

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
campus_envs = [list(sys.stdin.readline()) for _ in range(n)]
d_pos = [(1,0), (-1,0), (0,1), (0,-1)]

start_pos = [0, 0]
ans = 0

def validate_pos(x, y, n, m, v_p, c_v):
    if (0 <= x < n) and (0 <= y < m) and not ([x, y] in v_p) and c_v[x][y] != 'X':
        return True
    else:
        return False

for campus in campus_envs: # 시작 좌표 구하기
    if 'I' in campus:
        start_pos[0] = campus.index('I')

    start_pos[1] += 1

queue = deque()
visited_path = deque()
queue.append(start_pos)
visited_path.append(start_pos)

while len(queue) != 0:
    x, y = queue.popleft()

    for dx, dy in d_pos:
        new_x = x + dx
        new_y = y + dy

        if validate_pos(new_x, new_y, n, m, visited_path, campus_envs):
            queue.append([new_x, new_y])
            visited_path.append([new_x, new_y])

for x, y in visited_path:
    if campus[x][y] == 'P':
        ans += 1

if not ans:
    print("TT")
else:
    print(ans)

결과: 시간 초과 😭

visited_path에 [x, y] in v_p 와 같이 리스트를 순회하며 확인하는 과정에서 시간 복잡도가 너무 커져서 시간 초과가 난 것 같다

Idea 2️⃣

시간 초과를 해결하기 위해, 탐색하면서 동시에 만나는 사람 수를 세면 마지막에 visited_path를 순회하는 과정을 없앨 수 있겠다!

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
campus_envs = [list(sys.stdin.readline()) for _ in range(n)]
d_pos = [(1,0), (-1,0), (0,1), (0,-1)]

start_pos = [0, 0]
ans = 0

def validate_pos(x, y, n, m, v_p, c_v):
    if (0 <= x < n) and (0 <= y < m) and not ([x, y] in v_p) and c_v[x][y] != 'X':
        return True
    else:
        return False

for campus in campus_envs: # 시작 좌표 구하기
    if 'I' in campus:
        start_pos[0] = campus.index('I')

    start_pos[1] += 1

queue = deque()
visited_path = deque()
queue.append(start_pos)
visited_path.append(start_pos)

while len(queue) != 0:
    x, y = queue.popleft()

    for dx, dy in d_pos:
        new_x = x + dx
        new_y = y + dy

        if validate_pos(new_x, new_y, n, m, visited_path, campus_envs):
            if campus_envs[new_x][new_y] == 'P':
                ans += 1
            queue.append([new_x, new_y])
            visited_path.append([new_x, new_y])

if not ans:
    print("TT")
else:
    print(ans)

결과: 또 시간 초과 😱

여전히 in 연산자를 사용해서 방문 여부를 확인하는 부분이 문제라고 판단했다
이중 반복문 안에서 계속 리스트를 순회하니 시간 초과가 날 수밖에 없겠다고 생각했다

Idea 3️⃣ (성공! 🎉)

결국 시간 복잡도를 줄이기 위해 visited_path를 2차원 배열로 만들어서 인덱스로 바로 접근할 수 있도록 개선해야겠다고 생각했음. 이렇게 하면 O(1)의 시간 복잡도로 방문 여부를 확인할 수 있으니까.

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
campus_envs = [list(sys.stdin.readline()) for _ in range(n)]
visited_path = [[False for _ in range(m)] for _ in range(n)]
d_pos = [(1,0), (-1,0), (0,1), (0,-1)]

start_pos = [0, 0]
ans = 0

for i in range(n):
    for j in range(m):
        if campus_envs[i][j] == 'I':
            start_pos[0], start_pos[1] = i, j
    
queue = deque()
queue.append(start_pos)
visited_path[start_pos[0]][start_pos[1]] = True

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

    for dx, dy in d_pos:
        new_x = x + dx
        new_y = y + dy

        if 0 <= new_x < n and 0 <= new_y < m and not visited_path[new_x][new_y] and campus_envs[new_x][new_y] != 'X':
            if campus_envs[new_x][new_y] == 'P':
                ans += 1
            queue.append([new_x, new_y])
            visited_path[new_x][new_y]=True

if not ans:
    print("TT")
else:
    print(ans)

결과: 성공! ✅

방문 기록을 2차원 배열로 바꾸니 시간 복잡도 문제가 해결되면서 드디어 성공할 수 있었다

개선할 부분 🤔

시작 위치를 찾는 과정을 이중 반복문 대신 더 효율적인 방법으로 개선할 수 있을 것 같다