백준 11448번
https://www.acmicpc.net/problem/11448

문제

후기

⏰ 풀이시간 30분 ++⏰

맞힌 사람이 많지 않은 그래프 문제를 풀기 위해 풀은 사람이 적은 순으로 정렬해서 찾은 문제다.

영어로 되어있어 꽤(?) 오랜 시간에 걸려 문제를 이해하고 풀기 시작한 문제다.

기본적인 틀은 기타 DFS 문제들과 같으며, 상하좌우대각선을 탐색한다.

W를 발견하면 W가 다른 땅으로 뻗어 나가는데( 감염시키듯이 )

이로 인해 w가 몇개의 "-" 하이폰을 전염시킬 수 있는가에 대한 문제다.

"w"를 만나면 dfs를 시작하고 , 방문처리하며 , 최종적으로 몇개의 하이폰을 w로 바꿨는지

출력하면 된다.

나의 풀이

import sys
input= sys.stdin.readline
sys.setrecursionlimit(10**7)

dx = [-1,-1,-1,0,0,1,1,1] #상하좌우 대각선
dy = [-1,0,1,-1,1,-1,0,1]

def dfs(x,y):
    global result
    if x<=-1 or x>=N or y<=-1 or y>=N:
        return False

    for i in range(8): 
        nx = x + dx[i]
        ny = y + dy[i]

        if nx<=-1 or nx>=N or ny<=-1 or ny>=N:
            continue
        
 
        if graph[nx][ny]=="-": #하이폰을 만나면
            result+=1
            graph[nx][ny] ="w" #w로 바꾸며, 결과값이 1 증가된다. 
            dfs(nx,ny)
            
    return True
        
T = int(input())
for _ in range(T):
    N = int(input())
    graph = []
    result = 0
    for _ in range(N):
        graph.append(list(map(str,input().rstrip())))
    visited = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if graph[i][j]=="w" and not visited[i][j] : #dfs후 결과출력
                dfs(i,j)
    print(result)