Tag: grid graph

N, M = map(int, input().split())
grid = [list(input().strip()) for _ in range(M)]
visited = set()

dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(x, y, team):
    q = deque([(x, y)])
    visited.add((x, y))
    count = 1
    
    while q:
        x, y = q.popleft()
        
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            
            if not(0 <= nx < M and 0 <= ny < N):
                continue
            if (nx, ny) in visited:
                continue
            if grid[nx][ny] != team:
                continue
            visited.add((nx, ny))
            q.append((nx, ny))
            count += 1
    return count

white_power = 0
blue_power = 0

for i in range(M):
    for j in range(N):
        if (i, j) in visited:
            continue
        team = grid[i][j]
        count = bfs(i, j, team)
        if team == 'W':
            white_power += count ** 2
        else:
            blue_power += count ** 2

print(white_power, blue_power)

R, C = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(R)]

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

visited = [[False] * C for _ in range(R)]

q = deque()
for i, floor in enumerate(grid[0]):
    if floor == 1:
        q.append([0, i, 0])
        visited[0][i] = True

result = -1
while q:
    x, y, t = q.popleft()
    
    if x == R - 1:
        result = t
        break
    
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if not(0 <= nx < R and 0 <= ny < C):
            continue
        if grid[nx][ny] == 0 or visited[nx][ny]:
            continue
        
        q.append([nx, ny, t + 1])
        visited[nx][ny] = True

print(result)

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

dxy = ((1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1))

x, y = map(int, input().split())

enemy_list = [tuple(map(int, input().split())) for _ in range(M)]
result = [0] * M

q = deque([(x, y, 1)])
find_cnt = 0
visited = set([(x, y)])

while q:
    cur_x, cur_y, t = q.popleft()

    for dx, dy in dxy:
        n_x, n_y = cur_x + dx, cur_y + dy
        if (n_x, n_y) in visited:
            continue
        if (n_x, n_y) in enemy_list:
            enemy_idx = enemy_list.index((n_x, n_y))
            if result[enemy_idx] != 0:
                continue
            result[enemy_idx] = t
            find_cnt += 1
        if find_cnt == M:
            break
        q.append((n_x, n_y, t + 1))
        visited.add((n_x, n_y))
    else:
        continue
    break

print(*result)

1. (0, 0)에서 시작
2. 오른쪽(→), 아래(↓) 방향으로만 이동
3. 값이 1인 칸만 이동 가능
4. (M-1, N-1)에 도달하면 성공

from collections import deque

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

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

dyx = ((1, 0), (0, 1))

q = deque([(0, 0)])
visited = set([(0, 0)])

is_possible = False

if N == 1 and M == 1:
    is_possible = True

while q:
    y, x = q.popleft()
    for dy, dx in dyx:
        ny, nx = y + dy, x + dx
        if not(0 <= ny < M and 0 <= nx < N):
            continue
        if space[ny][nx] == 0:
            continue
        if (ny, nx) in visited:
            continue
        if (ny, nx) == (M - 1, N - 1):
            is_possible = True
            break

        q.append((ny, nx))
        visited.add((ny, nx))
    else:
        continue
    break

# print(visited)
print('Yes' if is_possible else 'No')

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

floor = [list(input()) for _ in range(N)]

def search_tiles(start, visited, tile_shape):
    # 타일 모양에 따라 탐색 방향 설정
    if tile_shape == '-':
        dy, dx = 0, 1
    else:
        dy, dx = 1, 0

    q = deque([start])
    while q:
        y, x = q.popleft()

        ny, nx = y + dy, x + dx

        # 범위 벗어났을 경우
        if not (0 <= ny < N) or not (0 <= nx < M):
            return 1
        # 이미 방문했을 경우
        if visited[ny][nx]:
            return 1
        # 타일 모양이 다를 경우
        if floor[ny][nx] != tile_shape:
            return 1

        q.append((ny, nx))
        visited[ny][nx] = True

visited = [[False] * M for _ in range(N)]
tile_cnt = 0

for y in range(N):
    for x in range(M):
        if visited[y][x]:
            continue
        tile_cnt += search_tiles((y, x), visited, floor[y][x])

print(tile_cnt)