acmicpc.net 2573(BFS), 11967(BFS), 9328(BFS)

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

파이썬으로 코딩하니 시간초과가 나서 C++로 바꿨더니 됬다. 망할.

#include <cstdio>
#include <queue>
using namespace std;

int n,m;
int _count;
int _y[] = {1,0,-1,0};
int _x[] = {0,-1,0,1};
int temp_arr[301][301];

void bfs(int y, int x)
{
	int visited[301][301]={0,};
	queue<pair<int, int>> q;
	q.push(make_pair(y,x));
	while(!q.empty())
	{
		int p0 = q.front().first;
		int p1 = q.front().second;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int ty = p0 + _y[i];
			int tx = p1 + _x[i];
			
			if(ty>n-1 || tx>m-1 || tx<0 || ty<0)
				continue;
			if(visited[ty][tx]==0 && temp_arr[ty][tx] > 0)
			{
				temp_arr[ty][tx] = 0;
				q.push(make_pair(ty,tx));
				visited[ty][tx] = 1;
			}
		}
	}
}

int main()
{
	int arr[301][301];
	int year = 0;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&arr[i][j]);

	while(1)
	{
		_count = 0;

		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				temp_arr[i][j] = arr[i][j];

		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(temp_arr[i][j] > 0)
				{
					_count++;
					bfs(i,j);
				}

		if(_count > 1)
		{
			printf("%d\n",year);
			break;
		}
		else if(_count==0)
		{
			printf("0\n");
			break;
		}
		int minus[301][301]={0,};
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(arr[i][j] > 0)
				{
					int c = 0;
					for(int k=0;k<4;k++)
					{
						int ti = i + _y[k];
						int tj = j + _x[k];
						if(ti>n-1 || tj>m-1 || ti<0 || tj<0)
							continue;
						if(arr[ti][tj]==0)
							c++;
					}
					minus[i][j] = c;
				}
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				arr[i][j] -= minus[i][j];
				if(arr[i][j]<0)
					arr[i][j] = 0;
			}
		year++;
	}
	return 0;
}

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

1. 불을 키면서 새로 불이 켜진 곳이 있으면 처음 위치(1,1)부터 다시 다 찾는다. 

2. 새로 켜진 곳이 없으면 탐색을 종료하고 하나하나 돌면서 불이 얼마나 켜져있는지 확인한다.

# -*- encoding: cp949 -*-
import Queue
def turn_up(y,x):
    global light
    visited = [[0 for j in xrange(n)] for i in xrange(n)]
    q = Queue.Queue()
    flag = False
    q.put([y,x]) 
    light[y][x] = 1
    visited[y][x] = 1
    while not q.empty():
        p = q.get()
        for s in arr[p[0]][p[1]]:
            if light[s[0]][s[1]]==0:
                flag = True
            light[s[0]][s[1]] = 1
        for i in xrange(4):
            ty,tx = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
            if ty>n-1 or tx>n-1 or ty<0 or tx<0:
                continue
            if visited[ty][tx]==0 and light[ty][tx]==1:
                q.put([ty,tx])
                visited[ty][tx] = 1
    return flag

n,m=map(int,raw_input().split())
arr = [[[] for j in xrange(n)] for i in xrange(n)]
light = [[0 for j in xrange(n)] for i in xrange(n)]
for i in xrange(m):
    x,y,a,b = map(int,raw_input().split())
    arr[x-1][y-1].append([a-1,b-1])
while True:
    if not turn_up(0,0):
        break

answer = 0
for i in xrange(n):
    for j in xrange(n):
        if light[i][j]==1:
            answer += 1
print answer

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

어렵다. 한 10번냈는데 10번다틀렸다. 한끗차이 에러가 있었었다.... 다른분이 알려줘서 그거 하나

고치고 AC떴다.

#include <cstdio>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
   
int h,w;
int doc;
int _y[] = {1,0,-1,0};
int _x[] = {0,-1,0,1};
string key;
char arr[150][150];
   
bool bfs(int y, int x) //새 키를 얻었으면 true 리턴.
{
    int visited[301][301]={0,};
    queue<pair<int, int>> q;
    q.push(make_pair(y,x));
    visited[y][x] = 1;
    while(!q.empty())
    {
        int p0 = q.front().first;
        int p1 = q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int ty = p0 + _y[i];
            int tx = p1 + _x[i];
               
            if(ty>h-1 || tx>w-1 || tx<0 || ty<0)
                continue;
            if(visited[ty][tx]==0 && arr[ty][tx]=='.')
            {
                q.push(make_pair(ty,tx));
                visited[ty][tx] = 1;
            }
            else if(arr[ty][tx]>='A' && arr[ty][tx]<='Z')
            {
                for(int k=0;k<key.length();k++)
                {
                    if(arr[ty][tx]+32==key[k])
                    {
                        arr[ty][tx] = '.';
                        q.push(make_pair(ty,tx));
                        visited[ty][tx] = 1;
                    }
                }
            }
            else if(arr[ty][tx]>='a' && arr[ty][tx]<='z')
            {
                bool keyadd = true;
                for(int k=0;k<key.length();k++)
                {
                    if(arr[ty][tx]==key[k])
                    {
                        keyadd = false;
                        break;
                    }
                }
                if(keyadd)
                {
                    key += arr[ty][tx];
                    arr[ty][tx] = '.';
                    return true;
                }
                arr[ty][tx] = '.';
                q.push(make_pair(ty,tx));
                visited[ty][tx] = 1;
            }
            else if(arr[ty][tx]=='$')
            {
                arr[ty][tx]='.';
                q.push(make_pair(ty,tx));
                visited[ty][tx] = 1;
                doc++;
            }
        }
    }
    return false;
}
   
bool check(int i, int j) //새 키를 얻었으면 true 리턴하는 함수
{
    if(arr[i][j]=='.')
    {
        if(bfs(i,j)) 
            return true;
    }
    else if(arr[i][j]=='$')
    {
        doc++;
        arr[i][j] = '.';
        if(bfs(i,j))
            return true;
    }
    else if(arr[i][j]>='a' && arr[i][j]<='z')
    {
        bool keyadd = true;
        for(int k=0;k<key.length();k++)
        {
            if(arr[i][j]==key[k])
            {
                keyadd = false;
                break;
            }
        }
        if(keyadd) //새로운 키를 얻었으면
        {
            key += arr[i][j]; //추가하고
            arr[i][j]='.'; 
            return true; //0행부터 다시 다검사
        }
        arr[i][j]='.'; //새 키가 아니면 그냥 공백으로 만들고
        if(bfs(i,j)) //탐색
            return true;
    }
    else if(arr[i][j]>='A' && arr[i][j]<='Z')
    {
        for(int k=0;k<key.length();k++)
        {
            if(arr[i][j]+32 == key[k])
            {
                arr[i][j] = '.';
                if(bfs(i,j))
                    return true;
            }
        }
    }
    return false;
}
  
int main()
{
    int t;
    cin>>t;
    for(int k=0;k<t;k++)
    {
        scanf("%d %d",&h,&w);
        for(int i=0;i<h;i++)
            scanf("%s",arr[i]);
        cin>>key;
        doc = 0;
        int i = 0;
        while(i < h)
        {
            if(i==0 || i==h-1)
            {
                for(int j=0;j<w;j++)
                    if(check(i,j))
					{
                        i = -1;
						break;
					}
            }
            else
            {
                if(check(i,0))
                    i = -1;
                if(check(i,w-1))
                    i = -1;
            }
            i++;
        }
        printf("%d\n",doc);
    }
    return 0;
}